2060: 宝典2第一章最接近点对问题

【问题描述】最接近点对问题（nearest.cpp/c/pas）HDU 1007

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

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

【输入格式】

输入文件为nearest.in，第一行为点的个数n，且2≤n≤60000；接下来n行：每行两个实数：x y，表示一个点的行坐标和列坐标，中间用一个空格隔开。

【输出格式】

输出文件为nearest.out，仅一行，为一个实数，表示最短距离的一半，精确到小数点后面２位。

【输入样例】

3                                              

1 1

1 2

2 2

【输出样例】

0.50