单点时限: 5.0 sec
内存限制: 256 MB
这个题目目前对于大家会有点难度,有兴趣的同学可以研究一下,这种题目才是分治的精髓所在。
前段时间 partychen 到吴泾去买东西,发现在步行街有一个赌博游戏,一个商人在地面上摆放了很多的小礼品,然后准备了很多大小相同的圆环,玩家可以到商人处花 5 块钱买一个圆环。然后站在一根白线外使用圆环套住自己想要的礼品。圆环套住的东西就归玩家所有。我这里描述的不是很清楚,但是我相信大家肯定也知道这个是什么游戏了。
出于商人的本性,他现在想邀请计算机的你,帮助他设计一个圆环,使得这个圆环最多只能套住一个小礼品。
为了让问题简单化,我们假设每一个小礼品都是平面上的一个点。如果点在圆环上也算套住。当然如果两个礼品重叠放置的话 那么圆环的半径显然会是 0。
他只要你求出这个圆环的半径。
输入数据有多组,每组测试数据第一行有一个正整数 $N$ ($2 \le N \le 100000$), 表示平面上有多少个点。然后有 $N$ 组实数对 $(x,y)$ ($-1000 \le x,y \le 1000$) 表示点的坐标。如果 $N=0$ 表示输出结束,并且不作处理。
对于每组测试数据,输出圆环的半径,结果保留两位小数。每个输出占一行。
2 0 0 1 1 2 1 1 1 1 3 -1.5 0 0 0 0 1.5 0
0.71 0.00 0.75