题目
3.8 给定 个点，其坐标为 ，要求使用分治策略求解设计算法，找出其中距离最近的两个点。两点间的距离公式为: (1）写出算法的伪代码; (2）编写C++程序实现这一算法; (3）分析算法的时间复杂度。
问题分析
建模
给定 个二维平面上的点，求一组欧几里得距离最近的点对。
求解
从答案的规模来看，每个点对都有可能是距离最近的点对，要想求得包含所有情况的最小答案就需要把所有点对都枚举一遍，时间复杂度是 。
不过正如排序算法一样，通过对原本混乱的点集规定一种规则，让其显得有序些并能进行前瞻剪枝。
下面我们介绍一种时间复杂度为 的分治算法来解决这个问题。该算法在 1975 年由 Franco P. Preparata 提出，Preparata 和 Michael Ian Shamos 证明了该算法在决策树模型下是最优的。
先将所有点按照 为第一关键字、 为第二关键字进行排序，并以 点为分界点，拆分为点集 :$$ \begin{aligned}A_1&={p_i\mid i=0\ldots m}\A_2&={p_i\mid i=m+1\ldots n-1}\end{aligned}
一直递归拆分到最后两个点时返回。求出两点集各自内部的最近点对，设距离为$h_1,h_2$，且令 $D=\min\{h_1,h_2\}$ 即最小值。 ## 编码 # 参考 [平面最近点对 - OI Wiki](https://oi-wiki.org/geometry/nearest-points/)