题目描述

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, than to 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.

Optimal route

Optimal route with added stone

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 of the input file contains two integers $w$ -- the width of the river and $n$ -- the number of stones in it $(1 \le w \le 10^{9}, 0 \le n \le 1000)$ .

Each of the following $n$ lines contains two integers $x_{i}, y_{i}$ -- the coordinates of the stones $(0 < x_{i} < w , −10^{9} \le y_i \le 10^{9}).$ Coordinates of all stones are distinct. River shores have coordinates $x = 0$ and $x = w$ .

输出格式

Write to the output file 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.

题目大意

题目描述

Fiona设计了一款新的电脑游戏《青蛙渡河》。在这个游戏中，玩家用石头当浅滩帮助青蛙过河。青蛙从河岸跳到第一个石滩，然后跳到第二个石滩等等，直到到达另一个岸。不幸的是，青蛙非常虚弱，它的跳跃距离非常有限。因此，玩家应该选择最佳路线——使穿越路线所需的最大跳跃最小化的路线。Fiona认为这个游戏不够有挑战性，所以她计划增加一种可能性，在河里放一块新石头。她要求你编写一个程序，确定新石头的位置，以最小化穿越最佳路线所需的最大跳跃。

输入格式

输入文件的第一行包含两个整数w n,表示河流的宽度和其中的石头数量（1<=w<=10^9，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）, 这块石头应尽量减少穿越最佳路线所需的最大跳跃，如果一个新的石头不能对最优路径提供任何改进，那么可以编写任意一对满足约束条件的石头，甚至可以与现有的一块石头重合。你的输出应精确到小数点后三位。

（样例数据见原题面）

说明与提示

时间限制：1s 内存限制：256MB

10 7
2 2
2 4
5 1
5 3
8 2
7 5
9 4

4.5 4.5

提示

Time limit: 1 s, Memory limit: 256 MB.