Task Description Day-1 ioi 2004 Athens Greece artemis icon

Task Description Day-1 ioi 2004 Athens Greece artemis



НазваTask Description Day-1 ioi 2004 Athens Greece artemis
Дата конвертації04.06.2013
Розмір20.92 Kb.
ТипЗадача
джерело
1. /artemis-ukr.doc
2. /empodia-ukr.doc
3. /farmer-ukr.doc
4. /hermes-ukr.doc
5. /overview1-ukr.doc
6. /overview2-ukr.doc
7. /phidias-ukr.doc
8. /polygon-ukr.doc
Task Description Day-1 ioi 2004 Athens Greece artemis
Задача відомий математик та філософ Піфагор вважав, що реальність має математичний характер. Сучасні біологи вивчають властивості біопослідовностей. Біопослідовність це послідовність m цілих чисел, яка
Task Description Day-2 ioi 2004 Athens Greece farmer
Task Description Day-1 ioi 2004 Athens Greece hermes
Задача гермес Артеміда
Задача фідій Фермер
Задача відомий давньогрецький скульптор Фідій готується до побудови чергового видатного монумента. Для цього йому потрібні мармурові прямокутні плитки заданих розмірів W
Task Description Day-1 ioi 2004 Athens Greece polygon

T
ask Description Day-1


IOI 2004

Athens

Greece artemis


Артеміда


ЗАДАЧА


Зевс надав Артеміді, богині дикої природи, прямокутну область для вирощування лісу. Ліва сторона області відповідає відрізку додатної частини вісі OY, нижня сторона відповідає відрізку додатної частини вісі OX, а точка (0,0) – лівому нижньому куту області. Зевс наполягав, щоб Артеміда саджала дерева тільки в тих точках області, які мають цілі координати. Артеміді подобалось, коли ліс виглядає природно, тому вона саджала дерева таким чином, щоб відрізок, який сполучає будь-яку пару дерев, не був паралельним вісім OX та OY.


Одного разу Зевс захотів, щоб Артеміда зрубила для нього дерева, слідуючи правилам:

  1. Зевс вимагає зрубити не менше T дерев.

  2. Щоб отримати прямокутну футбольну площадку для майбутніх футбольных перемог, Артеміда повинна зрубити всі дерева всередині деякої прямокутної області та жодного дерева зовні області.

  3. Сторони цієї прямокутної області повинні бути паралельними вісям OX та OY.

  4. Два протилежних кута області повинні находитися в місцях знаходження дерев, відповідно ці дерева також повинні бути зрублені.


Так як Артеміда любить дерева, вона хоче виконати умови, зрубив при цьому якомога менше дерев. Ви повинні написати програму, яка за інформацією про місцезнаходження дерев в лісі та про мінімальну кількість дерев T, яку необхідно зрубити, обирає область вирубки дерев для Артеміди.

ВХІДНІ ДАНІ



У вхідному файлі з ім’ям artemis.in перший рядок містить єдине ціле число N – кількість дерев у лісі. Другий рядок містить єдине ціле число T – мінімальна кількість дерев для вирубки. Наступні N рядків описують положення N дерев. Кожний з цих рядків містить два цілих числа: X та Y, x-координату і потім y-координату дерева.

ВІХІДНІ ДАНІ



Вихідний файл з ім’ям artemis.out повинен містити один рядок з двома цілими числами I та J, розділеними одним пропуском. Артеміда повинна розглядати I–те дерево з координатами, заданими в рядку I+2 вхідного файлу, і J–ое дерево з координатами, заданими в рядку J+2 вхідного файлу, як кути області для вирубки дерев. Порядок виводу цих двох чисел не суттєвий. Якщо існує декілька варіантів вибору такої пари дерев, ви повинні знайти і видати тільки один з них. Для всіх тестів існує хоча б один розв’язок.

ПРИКЛАД ВХІДНИХ ТА ВИХІДНИХ ФАЙЛІВ



artemis.in artemis.out


3

2

1 1

2 3

5 6

1 2

ОБМЕЖЕННЯ

У всіх тестах: 1<N≤20000, 0≤X,Y≤64000 і 1<TN.

У 50 % тестів: 1<N<5000.

02.06.13 Page of artemis



Схожі:

Task Description Day-1 ioi 2004 Athens Greece artemis iconAutodesk Software license agreement greece

Task Description Day-1 ioi 2004 Athens Greece artemis iconTask 1 albert einstein

Task Description Day-1 ioi 2004 Athens Greece artemis iconЗакон україни про кооперацію ( Відомості Верховної Ради України (ввр), 2004, n 5, ст. 35 ) ( Офіційне тлумачення до Закону див в Рішенні Конституційного Суду n 16-рп/2004 ( v016p710-04 ) від 11. 11. 2004 )

Task Description Day-1 ioi 2004 Athens Greece artemis iconDay 1 (20 may) day 2 (21 may)

Task Description Day-1 ioi 2004 Athens Greece artemis iconMy Day Off

Task Description Day-1 ioi 2004 Athens Greece artemis iconDate of birth (Day-Month-Year)

Task Description Day-1 ioi 2004 Athens Greece artemis iconFurniture task What pieces of furniture can you see on the pictures? Write them down and make up your own sentences

Task Description Day-1 ioi 2004 Athens Greece artemis iconThe 25th of December is Christmas Day. It's a happy holiday for many people in different countries

Task Description Day-1 ioi 2004 Athens Greece artemis iconEm item nr. Description

Task Description Day-1 ioi 2004 Athens Greece artemis iconЦивільний кодекс україни
Ову, 2003 р., N 52, ст. 2734, від 12 травня 2004 року n 1713-iv, ову, 2004 р., N 25, ст. 1629
Task Description Day-1 ioi 2004 Athens Greece artemis iconDescription of material to be conveyed

Додайте кнопку на своєму сайті:
Документи


База даних захищена авторським правом ©razom.znaimo.com.ua 2000-2014
При копіюванні матеріалу обов'язкове зазначення активного посилання відкритою для індексації.
звернутися до адміністрації
Документи