问题 1245 --最接近点对问题

1245: 最接近点对问题

时间限制: 1 Sec  内存限制: 128 MB
提交: 0  解决: 0
[提交][状态][讨论版][命题人:]

题目描述

楚继光和李旭琳一人骑着一辆自行车迎面而来,楚继光大叫:“小心,小心,你往左拐,我往右拐!”

呵呵,幸好他们骑的是自行车。更进一步,考虑在空中交通控制中,若将飞机作为空间移动的一个点来看待,则具有最大碰撞危险的2架飞机,就是这个空间中最接近的一对点。这类问题是计算几何学中研究的基本问题之一。下面我们着重考虑平面上的最接近点对问题。最接近点对问题的提法是:给定平面上n个点,找其中的一对点,使得在n个点的所有点对中,该点对的距离最小。严格地说,最接近点对可能多于1对。为了简单起见,这里只限于找其中的一对。

输入

第一行为点的个数n,且2≤n≤60000;接下来n行:每行两个实数:x y,表示一个点的行坐标和列坐标,中间用一个空格隔开。

输出

仅一行,为一个实数,表示最短距离的一半,精确到小数点后面2位。

样例输入

3
1 1
1 2
2 2

样例输出

0.50

提示

来源

 

[提交][状态]