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

Лягушачий брод

Лягушачий брод

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

Фиона разрабатывает новую компьютерную игру "Лягушачий Брод". В ней игрок помогает лягушке пересечь реку, используя выступающие из нее камни. Лягушка прыгает с берега реки до первого камня, затем на второй и так далее, пока не достигнет другого берега. К сожалению, лягушки довольно слабы и длина ее прыжка весьма ограничена. Игроку следует найти оптимальный маршрут - путь, который сведет к минимуму самый длинный прыжок.

prb7566.gif

Фиона считает, что эта игра не достаточно привлекательна, поэтому она планирует добавить возможность разместить новый камень в реке. Она просит Вас написать программу, которая определит такое расположение нового камня, который сведёт к минимуму самый большой прыжок, необходимый для прохождения оптимального маршрута.

Входные данные

Первая строка содержит два целых числа: w (1w10^9) - ширину реки и n (0n1000) - количество камней в ней.

Каждая из следующих n строк содержит два целых числа x[i], y[i] (0 < x[i] < w, −10^9y[i]10^9) - координаты камней. Координаты всех камней различны.

Река имеет координаты x = 0 и x = w.

Вывести два действительных числа x[+] и y[+] (0 < x[+] < w, −10^9y[+]10^9) - координаты добавляемого камня. Этот камень должен минимизировать наибольший прыжок в оптимальном маршруте. Если новый камень не может улучшить оптимальный путь, тогда вывести любую пару x[+] и y[+] удовлетворяющую заданным ограничениям, она может даже совпадать с одним из существующих камней.

Ответ выводить с точностью до трех десятичных знаков.

Пример

Входные данные #1
10 7
2 2
2 4
5 1
5 3
8 2
7 5
9 4
Выходные данные #1
4.5 4.5
Источник 2015 ACM NEERC, Semifinals, December 6, Problem F