Задача №111144. Перекресток
Страна Квадроляндия представляет собой квадрат N × N клеток. Ее жители используют систему координат, в которой левый нижний угол квадрата имеет координаты (0, 0), правый верхний: (N, N). В Квадроляндии находятся K городов, каждый в точке с целыми координатами. Жители Квадроляндии перемещаются по стране параллельно осям координат. Для ускорения поездок в соседние страны правительство решило построить две скоростные автомагистрали. Автомагистрали должны быть перпендикулярными между собой и параллельными осям координат. Каждая магистраль будет соединять две противоположные стороны квадрата.
Расстоянием от города до магистралей будет расстояние от города до ближайшей из них. Правительство решило разместить магистрали так, чтобы максимальное расстояние от городов до магистралей было минимально возможным.
Напишите программу, которая по длине стороны квадрата и расположению городов найдет оптимальное расстояние и расположение магистралей.
В первой строке входного файла содержатся два целых числа: N (1 ≤ N ≤ 1 000 000) и K (1 ≤ K ≤ 40 000) –– длина стороны квадрата и количество городов соответственно. Последующие K строк содержат по два целых числа — координаты городов (от 0 до N).
В единственной строке выходного файла выведите три целых числа — искомое оптимальное расстояние от самого удаленного города до ближайшей к нему магистрали, и координаты точки пересечения магистралей (перекрестка). Если оптимальных ответов несколько, выведите любой из них.
4 3
1 1
2 2
3 3
1 2 2
Подзадача 1. N ≤ 50, K ≤ 50. Решение оценивается в 35 баллов.
Подзадача 2. K ≤ 200. Решение оценивается в 15 баллов.
Подзадача 3. K ≤ 2 000. Решение оценивается в 15 баллов.
Подзадача 4. Дополнительные ограничения отсутствуют. Решение оценивается в 35 баллов.
Подзадачи являются вложенными, т.е. баллы за подзадачу ставятся только при прохождении всех меньших подзадач.