最近点对

最近点对

设\(p_i = (x_i,y_i)\)，表示平面上的一个点。

对于给定的点集\(S\)，求最近点对。

很容易想到\(O(n^2)\)的算法。

计算每一对点的距离，然后取最小值。

但今天看分治的时候看到一种\(O(nlogn)\)的算法。

我们将点集合\(S\)按照\(x\)为第一关键字，\(y\)为第二关键字的大小升序排列，然后在拆分成集合大小相同的\(S_1\)和\(S_2\)。

根据分治的想法，最近点对只会有三种情况：

• 两个点都在\(S_1\)集合中


• 两个点都在\(S_2\)集合中


• 一个在\(S_1\)一个在\(S_2\)。

前面两种可以递归的寻找，所以问题在于处理第三种情况。

假设情况1的最近点对距离为\(h_1\)，情况2的最近点对距离为\(h_2\)，\(h = min(h_1,h_2)\)。

用\(OIwiki\)上的这张图来观察一下：



对于情况3的情况，所选的点对最好是位于中间中间轴左右\(h\)的区域内比较好，这个区域就是上图的\(B\)。

上图是在\(x\)方向考虑，现在考虑\(y\)方向。

对于每一个在\(B\)中的\(p_i\)，只需要找到另外一个点\(p_j\)，且纵坐标绝对值之差小于\(h\)，考虑到重复的问题，我们让\(p_j\)的纵坐标大于\(p_i\)的纵坐标。有一个神奇的证明表示\(p_j\)的个数最大为7。

于是对于情况3我们有了一个算法：

1. 构建\(B\)


2. 将\(B\)按照纵坐标排序


3. 对于每一个\(p_i\)，找到最近距离更新答案

接下来就是使用分治法解决问题了，时间复杂度为\(O(nlogn)\)【虽然不太会证明这个问题】

#include
#include
#include
#include
#include