#P2498. [SDOI2012] 拯救小云公主
[SDOI2012] 拯救小云公主
题目描述
英雄又即将踏上拯救公主的道路……
这次的拯救目标是 —— 爱和正义的小云公主。
英雄来到 boss 的洞穴门口,他一下子就懵了,因为面前不只是一只 boss,而是上千只 boss。当英雄意识到自己还是等级 的时候,他明白这就是一个不可能完成的任务。
但他不死心,他在想,能不能避开 boss 去拯救公主呢,嘻嘻。
boss 的洞穴可以看成一个矩形,英雄在左下角 ,公主在右上角 。英雄为了避开 boss,当然是离 boss 距离越远越好了,所以英雄决定找一条路径使到距离 boss 的最短距离最远。
Ps: 英雄走的方向是任意的,但是不能走出矩形的范围。即英雄可以到达矩形范围内的任意一个点(没有必要是整点)
你可以帮帮他吗?
当英雄找到了美丽漂亮的小云公主,立刻就被 boss 包围了!!!英雄缓闭双眼,举手轻挥,白光一闪后使用了回城卷轴,回到了城堡,但只有小云公主回去了……因为英雄忘了进入回城的法阵了。
输入格式
第一行,输入三个整数, 表示 boss 的数目,、 表示矩形的大小;
接下来 行,每行分别两个整数,表示 boss 的位置坐标。
输出格式
输出一个小数,表示英雄的路径离 boss 的最远距离,精确到小数点后两位。
1 3 3
2 2
1.00
1 3 3
3 1
2.00
提示
数据范围
对于 数据,boss 坐标范围小于等于 ;
对于 数据,;
对于 数据,。