Лягушачий брод
Лягушачий брод
Фиона разрабатывает новую компьютерную игру "Лягушачий Брод". В ней игрок помогает лягушке пересечь реку, используя выступающие из нее камни. Лягушка прыгает с берега реки до первого камня, затем на второй и так далее, пока не достигнет другого берега. К сожалению, лягушки довольно слабы и длина ее прыжка весьма ограничена. Игроку следует найти оптимальный маршрут - путь, который сведет к минимуму самый длинный прыжок.
Фиона считает, что эта игра не достаточно привлекательна, поэтому она планирует добавить возможность разместить новый камень в реке. Она просит Вас написать программу, которая определит такое расположение нового камня, который сведёт к минимуму самый большой прыжок, необходимый для прохождения оптимального маршрута.
Входные данные
Первая строка содержит два целых числа: w (1 ≤ w ≤ 10^9
) - ширину реки и n (0 ≤ n ≤ 1000) - количество камней в ней.
Каждая из следующих n строк содержит два целых числа x[i]
, y[i]
(0 < x[i]
< w, −10^9
≤ y[i]
≤ 10^9
) - координаты камней. Координаты всех камней различны.
Река имеет координаты x = 0 и x = w.
Вывести два действительных числа x[+]
и y[+]
(0 < x[+]
< w, −10^9
≤ y[+]
≤ 10^9
) - координаты добавляемого камня. Этот камень должен минимизировать наибольший прыжок в оптимальном маршруте. Если новый камень не может улучшить оптимальный путь, тогда вывести любую пару x[+]
и y[+]
удовлетворяющую заданным ограничениям, она может даже совпадать с одним из существующих камней.
Ответ выводить с точностью до трех десятичных знаков.
Пример
10 7 2 2 2 4 5 1 5 3 8 2 7 5 9 4
4.5 4.5