Задача №112519. Артемида
Зевс подарил Артемиде, богине охоты, прямоугольный участок земли, чтобы вырастить лес. Левая сторона этого участка — это отрезок неотрицательного луча оси ординат, нижняя сторона — отрезок неотрицательного луча оси абсцисс, а (0, 0) — левый нижний угол участка. Зевс сказал Артемиде выращивать деревья только в точках с целыми координатами.
Артемида любит, когда лес выглядит естественно, и поэтому в её лесу любая прямая, проходящая через два дерева, не параллельна ни оси абсцисс, ни оси ординат.
Иногда Зевс хочет, чтобы Артемида вырубила для него деревья. Деревья должны быть вырублены так, чтобы выполнялись следующие условия:
- Зевс хочет, чтобы для него было вырублено хотя бы T деревьев.
- Чтобы потом построить прямоугольное футбольное поле для будущих футбольных успехов, Артемида должна вырубить все деревья внутри и на границе некоторой прямоугольной площадки, и ни одно дерево вне этой площадки.
- Стороны этой площадки должны быть параллельны осям координат.
- В двух противоположных углах площадки должны быть расположены деревья (которые будут вырублены).
Так как Артемида любит деревья, она хочет выполнить все условия таким образом, чтобы пришлось вырубить как можно меньше деревьев. Напишите программу, которая по информации о лесе и минимальному количеству деревьев T , которые должны быть вырублены, выбирает площадку, на которой Артемида будет вырубать деревья.
Первая строка ввода содержит единственное число N — количество деревьев в лесу ( 1 < N ≤ 20 000 ). Вторая строка содержит единственное число T — минимальное количество деревьев, которые должны быть вырублены ( 1 < T ≤ N ). Следующие N строк описывают расположение деревьев. Каждая из этих строк содержит по два целых числа X и Y — координаты дерева ( 0 ≤ X , Y ≤ 64 000 ). Решения, работающие только для N < 5000 , будут оцениваться из 50 баллов.
Вывод должен содержать единственную строку, в которой записано два целых числа I и J , разделённых пробелом: Артемида должна вырубить деревья на площадке, углами которой будут деревья с номерами I и J (это те деревья, которые описаны в строках входного файла с номерами I + 2 и J + 2 ). Эти числа можно выводить в любом порядке. Возможно, есть несколько способов выбрать эти деревья, и в этом случае вы должны вывести любую из подходящих пар. Гарантируется, что во всех тестах жюри существует хотя бы одно решение.
3 2 1 1 2 3 5 6
1 2