比赛场次 292
比赛名称 20160309
比赛状态 已结束比赛成绩
开始时间 2016-03-09 19:00:00
结束时间 2016-03-09 22:00:00
开放分组 全部用户
注释介绍
题目名称 拯救小云公主
输入输出 dis.in/out
时间限制 1000 ms (1 s)
内存限制 256 MiB
测试点数 10 简单对比
用户 结果 时间 内存 得分
Gravatarzys AAAAAAAAAA 1.217 s 69.48 MiB 100
GravatarFmuckss AAAAAAAAAA 1.310 s 138.16 MiB 100
Gravatar农场主 AAAAAWWTAT 3.698 s 0.38 MiB 60

拯救小云公主

★★   输入文件:dis.in   输出文件:dis.out   简单对比
时间限制:1 s   内存限制:256 MiB

【题目描述】


英雄又即将踏上拯救公主的道路……

   这次的拯救目标是——爱和正义的小云公主。

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

   但他不死心,他在想,能不能避开boss去拯救公主呢,嘻嘻。

   Boss的洞穴可以看成一个矩形,英雄在左下角(1,1),公主在右上角(row,line)。英雄为了避开boss,当然是离boss距离越远越好了,所以英雄决定找一条路径使到距离boss的最短距离最远。

Ps:英雄走的方向是任意的。

   你可以帮帮他吗?

   当英雄找到了美丽漂亮的小云公主,立刻就被boss包围了!!!英雄缓闭双眼,举手轻挥,白光一闪后使用了回城卷轴,回到了城堡,但只有小云公主回去了……因为英雄忘了进入回城的法阵了。


【输入格式】


第一行,输入三个整数,n表示boss的数目,row,line表示矩形的大小;

   接下来n行,每行分别两个整数表示boss的位置坐标。


【输出格式】

输出一个小数,表示英雄的路径离boss的最远距离,精确到小数点后两位。

【样例输入1】

1 3 3
2 2 

【样例输出1】

1.00
【样例输入2】
1 3 3
3 1

【样例输出2】

2.00

【提示】


数据范围:

20%数据,boss坐标范围小于等于50;

60%数据,n<=1500;

100%数据,n<=3000;


【来源】

在此键入。