|
Сигнальная вышка
(Время: 5 сек. Память: 128 Мб Сложность: 53%)
На карте изображена прямоугольная сетка из M строк и K столбцов. В некоторых клетках расположены маяки (всего N штук). Координаты маяка задаются парой (r, c) – номер строки и номер столбца (строки нумеруются сверху вниз от 1, столбцы слева направо от 1).
Один из маяков хотят превратить в сигнальную вышку. Вышка посылает сигнал строго по линиям сетки в четырёх направлениях: вверх, вниз, влево, вправо. Считается, что сигнал «покрывает» клетку, если она лежит на одном из этих лучей и находится между выбранным маяком и ближайшей преградой. Преградой является либо первый маяк на пути луча в этом направлении, либо граница карты, если маяков на пути нет. Клетка, в которой стоит выбранный маяк, не считается покрытой.
Нужно выбрать маяк для установки вышки так, чтобы число покрытых клеток было максимальным. Если оптимальных маяков несколько, выбирают тот, который стоит в самом правом столбце, если и таких несколько – в самой верхней строке среди них.
Входные данные
В первой строке входного файл INPUT.TXT даны три натуральных числа N, M, K (1 ≤ N, M, K ≤ 2×105). В следующих N строках даны координаты маяков: ri ci (1 ≤ ri ≤ M, 1 ≤ ci ≤ K). Гарантируется, что все координаты различны.
Выходные данные
В выходной файл OUTPUT.TXT выведите два натуральных числа: номер строки маяка, где нужно установить вышку, максимальное число покрытых клеток.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 8 6 7
1 5
2 2
2 4
3 3
4 4
5 7
6 1
6 4 | 5 11 |
Автор задачи
Владимир Игоревич Лукьянчиков
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |
