数据结构与算法专题题库

1063. 最近点对

单点时限: 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$ 表示输出结束,并且不作处理。

输出格式

对于每组测试数据,输出圆环的半径,结果保留两位小数。每个输出占一行。

样例

Input
2
0 0
1 1
2
1 1
1 1
3
-1.5 0
0 0
0 1.5
0
Output
0.71
0.00
0.75
不限期开放

题目列表