Closest Pair

平面最近点对算法

见oj/1299.cpp和oj/1299_multiset.cpp.

问题

给定平面上$n(n\geq 2)$个点，求欧几里得距离最近的两个点。

方法一：暴力

枚举所有点对，$O(n^2)$。

代码

方法二：分治

一个很优美的思路。

先将所有点按照$x$坐标排序。假设当前我们想要处理下标$[l, r)$内的点，我们把这个区间分成两部分：$m=\lfloor\frac{l+r}{2}\rfloor$，分别递归找到$[l, m)$和$[m, r)$内的最近点对距离$d_1$和$d_2$，令当前最短距离$d=\min(d_1, d_2)$。

现在只需要考虑跨越左右两边的点。假设下标为$i$的点坐标是$(x_i, y_i)$。首先观察到以下两点：

• $x_i \in (x_m - d, x_m + d)$的点才是有意义的，否则一定不会对答案有贡献（离中线太远了）；
• 每个满足前一个条件的点$i$，只需要考虑$(x_m - d, x_m + d) \times (y_i - d, y_i]$内的点，其他要么不会产生贡献，要么会被其他的点计算过。

令区域$B_i = (x_m - d, x_m + d) \times (y_i - d, y_i]$，我们现在证明$B_i$中除了$i$本身，最多还有$7$个点：

• 把$B_i$划分成$\frac{d}{2}\times \frac{d}{2}$的小块区域，这样会得到$8$个子区域。
• 每个小区域内，最多只有一个点，因为两个点的距离不会超过$\frac{d}{\sqrt 2}$，而我们知道每个区域内的点都属于左边或都属于右边，两点之间距离是不会小于$d$的。
• $i$号点在且仅在一个小区域内，其他$7$个区域最多每个区域一个点，所以最多$7$个点。

也就是说，每个点只需要遍历最多$7$个候选点。总复杂度为：

• 按$x$排序，$O(n\log n)$；
• 递归函数：$T(n) = 2T(n/2) + O(n\log n) + O(n)$，其中$O(n\log n)$是按照$y$排序，$O(n)$是遍历中线旁边的点。这样$T(n) = O(n\log^2 n)$
• 所以总复杂度为$O(n\log^2 n)$。

但其实还可以进一步优化：递归处理完左右区间后，我们已经不需要$x$升序，所以我们不妨让每次函数执行完，就把当前区间按照$y$从小到大排序，那么左右区间都这么排好后，只需要一个$O(n)$的归并就好了。这样总复杂度就是$O(n\log n)$。

代码

方法三：暴力？

观察方法二，发现$7$个点条件并不需要对半分，只要分成两块一定有这个条件。

还是先按照$x$从小到大排序，假设我们现在已经处理好前$i-1$个点的最小距离$d$，现在考虑加入第$i$个点。那么可能对$i$产生贡献的点一定在$(x_i - d, x_i] \times (y_i - d, y_i + d)$区域内，这个区域内除了$i$也最多是$7$个点。

所以问题转化为如何快速找到这$7$个点。考虑维护一个multiset，按照$y$排序，每次遍历到新的$i$，就把横坐标$x_i - x_j \geq d$的节点都删掉，剩下只需要考虑$y$坐标在区域内，使用multiset::iterator遍历$i$周围的点就好了。

时间复杂度还是$O(n\log n)$，省去了递归，可能还会快一点？

代码