eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Артеміда

Артеміда

Зевс виділив Артеміді, богині дикої природи, прямокутну ділянку для вирощування лісу. Ліва сторона області відповідає відрізку додатньої частини осі \textbf{OY}, нижня сторона відповідає відрізку додатньої частини осі \textbf{OX}, а точка \textbf{(0, 0)} -- лівому нижньому куту області. Зевс забажав, щоб Артеміда вирощувала дерева лише у тих точках ділянкиі, які мають цілі координати. Артеміді подобалось, коли ліс виглядає природньо, тому вона саджала дерева таким чином, щоб відрізок, який з'єднує довільну пару дерев, не був паралельним осям \textbf{OX} та \textbf{OY}. Одного разу Зевс захотів, щоб Артеміда вирубала для нього дерева, дотримуючись наступних правил: \begin{enumerate} \item Зевс вимагає зрубати не менше \textbf{T} дерев. \item Щоб отримати прямокутню футбольну площадку для майбутніх футбольних перемог, Артеміда повинна зрубати усі деревая всередині деякої прямокутної області і жодного дерева поза областю. \item Сторони цієї прямокутної області повинні бути паралельні осям \textbf{OX} та \textbf{OY}. \item Два протилежних кути області повинні знаходитись у місцях розміщення дерев, відповідно ці дерева також повинні бути зрубані. \end{enumerate} Так як Артеміда любить деревья, вона хоче виконати умови, зрубавши при цьоум якомога менше дерев. Ви повинні написати програму, яка за інформацією про розміщення дерев у лісі та про мінімальну кількість дерев \textbf{T}, які необхідно зрубати, вибирає область вирубки дерев для Артеміди. \InputFile У вхідному файлі перший рядок містить одне ціле число \textbf{N} -- кількість дерев у лісі. Другий рядок містить одне ціле число \textbf{T} -- мінімальну кількість дерев для вирубки. Наступні \textbf{N} рядків описують положення \textbf{N} дерев. Кожен з цих рядків містить два цілих числа: \textbf{X} та \textbf{Y}, \textbf{x}-координату а потім \textbf{y}-координату дерева. Для усіх тестов \textbf{1} < \textbf{N} ≤ \textbf{20000}, \textbf{0} ≤ \textbf{X}, \textbf{Y} ≤ \textbf{64000} та \textbf{1} < \textbf{T} ≤ \textbf{N}. У \textbf{50}\% тестів: \textbf{1} < \textbf{N} < \textbf{5000}. \OutputFile Вихідний файл повинен містити один рядок з двома цілими числами \textbf{I} та \textbf{J}, відокремленими одним пропуском. Артеміда повинна розглядати \textbf{I}--те дерево з координатами, заданими у рядку \textbf{I+2} вхідного файлу, та \textbf{J}--те дерево з координатами, заданими у рядку \textbf{J+2} вхідного файлу, як кути області для вирубки дерев. Порядок виведення цих двох чисел не істотний. Якщо існує декілька варіантів вибору такої пари дерев, ви повинні знайти і вивести лише один з них. Для усіх тестів існує хоча б один розв'язок.
Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB
Вхідні дані #1
500
30
1272 1
4 5
5 7
1265 9
1264 10
14 11
17 12
1257 15
1254 18
23 19
24 22
1244 24
1243 27
35 29
39 30
1236 32
1233 34
43 37
46 40
1225 41
1224 44
54 45
58 46
1219 47
1218 49
66 52
70 53
1209 56
1207 60
82 63
86 67
1199 68
1195 69
91 72
94 74
1188 75
1187 78
100 82
103 86
1179 87
1178 88
112 89
114 92
1170 93
1169 95
122 96
123 99
1160 100
1156 104
132 106
134 107
1148 109
1145 113
141 114
144 118
1137 122
1133 126
150 128
153 130
1125 134
1121 138
159 141
162 143
1115 145
1111 146
169 148
170 149
1102 152
1101 155
180 158
183 161
1095 164
1094 165
192 166
194 167
1087 171
1085 175
204 177
205 181
1075 183
1073 185
215 189
217 191
1066 193
1062 197
227 199
229 200
1055 204
1053 207
238 209
241 213
1047 216
1044 218
249 222
250 225
1036 229
1033 232
258 233
262 237
1027 241
1026 242
268 246
269 247
1020 248
1019 251
278 253
280 255
1008 256
1004 259
291 262
292 266
996 270
992 274
297 276
300 278
987 279
983 280
305 283
306 287
974 291
972 292
313 296
316 300
963 301
961 304
326 307
3
...
Вихідні дані #1
Empty file.
  Yours Sincerely, CAP
Джерело IOI-2004