1454: 最近点对距离问题
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：11
解决：5
题目描述
给定平面上n个点，找其中的一对点，使得在n个点的所有点对中，该点对的距离最小。严格的说，最近点对可能多于一对。为了简单起见，这里只找一对。
输入
平面内各点的坐标，以（0，0）表示输入结束（每行一个点的坐标）
输出
距离最近的两点坐标。
样例输入 复制
1 3
1 2
1 2.8
1 -3
1 -2.5
1 -1
1 0
0 0样例输出 复制
the nearest lenght is: 0.20
the first point is:1 1.00 3.00
the second point is:3 1.00 2.80
提示
2<=n<=10000
点对的输出，先出现的为the first point，后出现的为the second point
分治算法 描述：
可以划一条垂线，把点集分成两半：PL和PR。于是最近点对或者在PL中，或者在PR中，或者PL，PR各有一点。
把三种距离情况定义为dL, dR, dC.
其中dL, dR可以递归求解，于是问题就变为计算dC。
设s=min(dL, dR). 通过观察能得出结论：如果dC<s,则只需计算dC。如果dC满足这样的条件，则决定dC的两点必然在分割线的s距离之内，称之为带（strip）
否则不可能满足dC<s, 于是缩小了需要考虑的点的范围。 