bzoj#P4219. 跑得比谁都快

跑得比谁都快

题目描述

n+e 又即将踏上拯救妹子的道路……

这次的拯救目标是——爱和正义的小叶妹子。

n+e 来到 boss 的洞穴门口,他一下子就懵了,因为面前不只是一只 boss,而是上万只 boss。当 n+e 意识到自己还是等级 1 的时候,他明白这就是一个不可能完成的任务。

但他不死心,他可是跑得比谁都快,他在想,能不能避开 boss 去拯救妹子呢?

Boss 的洞穴可以看成一个矩形,n+e 在左下角 (0,0)(0,0),妹子在右上角 (A,B)(A,B)。n+e 为了避开 boss,当然是离 boss 距离越远越好了,所以 n+e 决定找一条路径使到距离 boss 的最短距离最远。

PS:n+e 走的方向是任意的。

你可以帮帮他吗?

当 n+e 找到了美丽漂亮的小叶妹子,立刻就被 boss 包围了!!!n+e 缓闭双眼,举手轻挥,白光一闪后使用了回城卷轴,回到了城堡,但只有小叶妹子回去了……因为 n+e 忘了进入回城的法阵了。(然而并没有什么关系,他可是跑得比谁都快呢)

输入格式

第一行,输入三个数 N,A,BN,A,BNN 表示 boss 的数目,A,BA,B表示矩形的大小;

接下来 nn 行,每行两个数表示 boss 的位置坐标 (x,y)(x,y),保证 0xA,0yB0\le x\le A,0\le y\le B,并且坐标两两不同。

输出格式

输出一个小数,表示 n+e 的路径离 boss 的最远距离,精确到小数点后六位。

样例 #1

2 10 10
5 4
2 1
2.000000

样例 #2

2 10.000000 10.000000
2.500000 7.500000
7.500000 2.500000
3.535534

数据规模与约定

对于 100%100\% 的数据:N105N\le 10^5A,B2×105A,B\le 2\times 10^5

题目来源

By wjy1998