Froggy Ford#7566
Fiona designs a new computer game Froggy Ford. In this game, a player helps a frog to cross a river using stone fords. Frog leaps from the river's shore to the first stone ford, then the second one and so on, until it reaches the other shore. Unfortunately, frog is pretty weak and its leap distance is quite limited. Thus, a player should choose the optimal route — the route that minimizes the largest leap required to traverse the route.
Fiona thinks that this game is not challenging enough, so she plans to add a possibility to place a new stone in the river. She asks you to write a program that determines such a location of the new stone that minimizes the largest leap required to traverse the optimal route.
The first line contains two integers w~(1 \le w \le 10^9) — the width of the river and n~(0 \le n \le 1000) — the number of stones in it.
Each of the following lines contains two integers x_i, y_i~(0 < x_i < w, -10^9 \le y_i \le 10^9) — the coordinates of the stones. Coordinates of all stones are distinct.
River shores have coordinates x = 0 and x = w.
Write two real numbers x_+ and y_+~(0 < x_+ < w, -10^9 \le y_+ \le 10^9) — the coordinates of the stone to add. This stone shall minimize the largest leap required to traverse the optimal route. If a new stone cannot provide any improvement to the optimal route, then an arbitrary pair of x_+ and y_+ satisfying the constraints can be written, even coinciding with one of the existing stones.
Your answer shall be precise up to three digits after the decimal point.
Esempio 1