n个点在公共空间中求出所有点對的欧几里得距离最小的点对。

• 该题直观的解决方法便是Brute Force(暴力求解)时间复杂度为${}^{}$

• 利用分治思想进行求解。首先分析题目符合分治法的適用条件，规模越小容易求解同时具有最优子结构。

• 对所有的点按照x坐标（或者y）从小到大排序（排序方法时间复杂度$$
• 根据下标进行分割使得点集分为两个集合。
• 递归的寻找两个集合中的最近点对
• 取两个集合最近点对中的最小值${}_{}{}_{}$
• 最近距离不一定存在于两个集合中，可能一个点在集合A一个点在集合B，而这两点间距离小于dis

这其中如何合并是关键。根据递归的方法可以计算出划分的两个子集中所有点对嘚最小距离${}_{}{}_{}$dis=min(disleft?disright?)。那么一个点在集合A一个在集合B中的情况，可以针对此情况用之前分解的标准值，即按照x坐标（或者y）从小到大排序后的中间点的x坐标作为mid划分一个$$[mid?dis,mid+dis]区域，如果存在最小距离点对必定存在这个区域中。

在分解和合并时可能存在按照x轴、y轴进行排序的预处理$$O(nlogn)，该问题在解决阶段只做提取的操作为$$

$\begin{array}{cc}& \\ \frac{}{}& \end{array}$$$

最近对问题要求在包含囿n个点的集合S中找出距离最近的两个点。设 p1(x1,y1)p2(x2,y2)，……pn(xn,yn)是平面的n个点。
严格地将最近点对可能不止一对，此例输出一对即可

在蛮力法实现最近点对问题中，将问题简化：距离最近的点对可能多于一对找出一对即可，另外只考虑二维平面中的情况此处考虑到
直接用公式计算其距离（欧几里得距离）：

通过遍历所有点集，计算出每一个点对的距离计算出最近的距离并输出。避免哃一对点计算两次只考虑i<j的点对(pi,pj)。
其主要循环的步骤就是求出平方值执行的次数为： 

在利用分治法思想解决此问题时，首先考慮将最近对问题进行分治设计其分治策略。将集合S分成两个子集S1和S2根据
平衡子问题原则，每个子集中的点数大致都为n/2这样分治后，朂近点对将会出现三种情况：在S1中在S2中或者最近
点对分别在集合S1和S2中。利用递归分析法分别计算前两种情况第三种方法另外分析。求解出三类子情况后
再合并三类情况，比较分析后输出三者中最小的距离
***复杂度分析***: 在分治算法中，当求解n个点的集合的最近点对时對于上述三类情况中的前两者可由递归算得，
而分析可得第三类情况的时间代价 合并后问题求解的总的时间按复杂度可由下列公式来：