题意：
在一个平面当中分布着n个点。现在我们知道这n个点的坐标，要求找出这n个点当中距离最近的两个点的间距。
番外：
不知为何我第一时间想到的是距离最近的点，那他们起码是所有点中x最近，或者y最近，不可能x和y都不是最近的但是他们的距离最近，于是先按照坐标的x和y分别排一遍序，扫一遍就可以了。
不能这么简单吧？自己搞了个样例试了试，发现果然理所当然想的是不对的。
如有四个点：A(0,0) B(1,3) C(2,2) D(3,1)，那么按照x坐标排序是A B C D的顺序，按照y坐标排序是A D C B的顺序，而答案显示是AC距离最短。
也不知道为什么会有如此愚蠢的想法，很明显距离是二维计算，x^2+y^2，一维小，另一维度可能很大，所以不能作参考。
分析：
进入正题分析，如果我们要求出每两个点之间的距离，那么复杂度一定是O(n^2) 。如果存在更快的算法，那么我们肯定不能求出所有点对之间的距离，要去忽略一些点对间的距离不求，但如果我们没有去求所有的点对距离，如何判断我们的答案是对的并且没有遗漏呢？
如果我们仔细思考一下，会发现这个问题和排序其实非常类似。我们在排序的时候，表面上来看，要得出每两个点之间都存在的大小关系，我们要排序似乎也要用O(n^2)的时间获得这些关系。但实际上，我们都知道，无论是快速排序还是归并排序都可以做到用O(nlogn)的时间内完成排序。
无论是快速排序还是归并排序，本质上都是利用的分治法。那么这道题是否也可以使用分治法求解呢？答案当然是可以的。
分治法过程：
分治法的总体思路是先拆分，将整个的数据拆成两个部分，使用递归分别完成两个部分，然后再合并得到完整的结果。
在这个问题当中，我们要拆分数据也非常简单，只需要按照x轴坐标对所有点进行排序，然后选择中点进行分割即可。
拆分结束如下：
因为使用分治法，所以在下层递归中我们可以获得SL和SR中最近的两个点的距离。
现在考虑在已知SL，SR的最近点对的条件下如何合并的问题。
合并后的答案无非就是三个中的最小值：SL的最近点对，SR的最近点对，在边界两边的点组成的点对。
所以目前的问题就是如何求出在边界两边的点组成的点对的距离。要分析清楚这个问题不是非常容易，需要深入的思考。
首先我们通过递归调用可以获得左边部分SL的最短距离D1以及右边部分SR的最短距离D2。我们取D=min(D1,D2），也就是左右两边最短距离的最小值，这个是目前的答案（先不考虑在边界两边的点组成的点对）。
求出了D之后，我们就可以用它来限定在边界两边的点组成的点对这种情况了。
我们在左侧随便选择一个点p，对于点p而言，边界右侧所有的点都有可能与它构成最近点对吗？当然不是，有一些离得远的是明显不可能的，对于这些点我们没有必要一一遍历，直接都可以批量忽略。要想和p点构成最近点对，必须在如图这个虚线框起来的范围内。
这个虚线构成的框是一个长方形，它的宽是D，长是2D。这是怎么来的呢？其实很简单，对于p点来说，要想和他构成全局的最近点对，那么距离它的距离一定要小于目前的最优解D。既然距离要小于D，那么意味着它们的横纵坐标之差的绝对值必须也要小于D。
当然这个框只是我们直观看到的，在实际算法运行的时候是没有这个框的，我们只能根据坐标轴自己去进行判断某个点在不在框里。
这个框到底可以起到多大的作用呢？有了这个框就可以降低算法复杂度了吗？会不会出现右侧所有点都在框里的极端情况呢？（如左侧图）
对于框里的点我们有一个基本的要求，就是在这个框里的点，两两之间的距离不得小于D。如果小于D了就和我们刚才得到D是左右两侧最小距离的结论矛盾了。根据鸽笼原理，虚线框里的点的数量最多有6个（此处忽略证明），由此可见这个框的作用非常大！
表面上看起来我们所有的分析都结束了，但实际上还有一个问题没有解决。就是我们怎么样找到这6个点呢？显然只根据横坐标是不行的，这个时候就需要考虑纵坐标了。我们将点集分成左右两个部分之后，对右侧部分按照纵坐标进行排序，对于左侧的点(x, y)而言，我们只需要筛选出右侧满足纵坐标范围在(y - d, y + d)范围内的点，这样的点最多只有6个。我们可以利用二分法找到纵坐标大于 y - d的最小的点，然后依次枚举之后的6个点即可。在分治的时候需要先排序再递归。
总结：
最重要的一点是通过已得到的D1 D2得出D，再用D来限制合并操作。
代码实现：
本文主要对于解题思想进行分析，代码实现以及优化，这个博客写的很清楚明白：https://blog.csdn.net/qq_21050645/article/details/105518642