每天一个知识点：分治算法：最近点问题

在一个二维平面内，存在 N 个点，其中必然存在两个点 p1 = (x1, y1) 和 p2 = (x2,y2)，它们之间的欧几里得距离最短，即 的值最小。

如果存在 N 个点，那么就存在 对点间的距离。我们可以检查所有这些距离，得到一个很短的程序，不过这是一个花费 的算法。有没有更好的方法呢？

其实可以用分治法进行求解：

1. 将所有点按照 X，Y 坐标由小到大排序；
2. 设置一条中轴线，将点在平面上分成左右两边；
3. 递归的进行分割，计算，这里的计算分为三种：
   1. 计算左边的最近点距离；
   2. 计算右边的最近点距离；

   3. 比较左、右两边最近点距离，取较小值作为中间距离的参考，即下图中的 d。

      
      

需要说明的是，对于任意点 ，在最坏的情况下最多考虑 7 个点的 。这是因为这些点必定落在该带状区域左半部分的 dXd 方块内或者落在该带状区域右半部分的 dXd 方块内。另一方面，在每个 dXd 方块内的所有的点至少分离 d。在最坏的情形下，每个方块包含 4 个点，每个角上一个点。这些点中有一个是 ，最多还剩下 7 个点要考虑。

这种策略保证了整个算法是 的。