问题描述： 给定平面上n个点，找出距离最近的两个点。
思考过程： 1）对于这种问题，我们首先想到的求解方法就是求出所有点对的距离，并找出最近的那个，当然这个是个显而易见的方法，具体过程大体可以警醒如下描述。
① 定义变量
N (点的数目)，X[N] (点的x坐标值)，Y[N]（点的y坐标值），closest（最近的值），P（最近点对的一个点），Q（最近点对的另一个点）。
② 依次扫描并比较出最近点对
初始化closest=get_len(X[1],Y[1],X[2],Y[2]);
P=(X[1],Y[1]);Q=(X[2],Y[2]);
For i=1:N
For j=i+1:N
Tmp=get_len(X,Y,X[j],Y[j]);
If Tmp < closest
Closest=Tmp;
P=(X,Y);
Q= (X[j],Y[j]);
End If
End For
End For
这样运行后就可以求出所有的点中的最近的点对值，然而这是一种Brute-force（蛮力法），当然时间复杂度也是非常不能令人满意的Q(n2)。
2）对于1）中的算法基本上很简单而且很容易想到，的确，对于一些问题，人们往往想的简单做的难，想的难就做的简单啦(呵呵)。在此，可以利用分治法来对问题求解。具体算法步骤如下：
① 将所有的点按X坐标值排序，然后平均等分成两个部分PL与PR。在左右分开处画个分割线part_line。（如下图）
② 找出PL中的最近值与PR中的最近值分别为dL，dR。
③ 令d=min（dL，dR）；现在，问题来了，d一定最小么？
回答是相当确定的，就是肯定不是最小的。原因也显而易见，就是最近点对可能出现在PL与PR的分割处。
④ 根据③中的问题，可以以part_line为中心左右|d|的距离里的点考虑（为什么？超过这个距离显然不需要 考虑啦，因为距离一定会大于d啦~~~）。现在，问题又来了，如何取得这个范围内的最近点呢？蛮力？全搜索计算？对！不行的这是，可能所有的点都落在这个范围里，就此一项我的时间复杂度就又会回到Q(n2)。怎么办？
⑤ 对于④中的问题，解决方法是这样的，将左右|d|范围里的点按Y值排序，然后依次从每个点出发做水平线，并在其之上d的距离做水平线，这样得到了一个2d*d的矩形，显然，在此矩形之外的点无需开率啦，可以证明，矩形内最多容下8个点（包括自己本身）。所以意味着在排好序的Y坐标点中，只需要考虑其后的7个点就行了，此外已有人证明了事实上只需要考虑其后的4个点就行啦。可见，这些的时间复杂度最多Q（N）。
⑥ 纵观整个过程，首先要对X坐标排序时间为O（NlogN），这是分治之前的预处理。然后问题分成了N/2规模，然后用Q（N）的复杂度得到中间的最近点对，然后可以在常数时间内得到最终的点对与最近值。So。。。T（N）=2T（N/2）+O（N），可以得到该算法的时间为O（NlogN）（即使加上一开始的排序预处理的时间复杂度）。
思考过程： 1）对于这种问题，我们首先想到的求解方法就是求出所有点对的距离，并找出最近的那个，当然这个是个显而易见的方法，具体过程大体可以警醒如下描述。
① 定义变量
N (点的数目)，X[N] (点的x坐标值)，Y[N]（点的y坐标值），closest（最近的值），P（最近点对的一个点），Q（最近点对的另一个点）。
② 依次扫描并比较出最近点对
初始化closest=get_len(X[1],Y[1],X[2],Y[2]);
P=(X[1],Y[1]);Q=(X[2],Y[2]);
For i=1:N
For j=i+1:N
Tmp=get_len(X,Y,X[j],Y[j]);
If Tmp < closest
Closest=Tmp;
P=(X,Y);
Q= (X[j],Y[j]);
End If
End For
End For
这样运行后就可以求出所有的点中的最近的点对值，然而这是一种Brute-force（蛮力法），当然时间复杂度也是非常不能令人满意的Q(n2)。
2）对于1）中的算法基本上很简单而且很容易想到，的确，对于一些问题，人们往往想的简单做的难，想的难就做的简单啦(呵呵)。在此，可以利用分治法来对问题求解。具体算法步骤如下：
① 将所有的点按X坐标值排序，然后平均等分成两个部分PL与PR。在左右分开处画个分割线part_line。（如下图）
② 找出PL中的最近值与PR中的最近值分别为dL，dR。
③ 令d=min（dL，dR）；现在，问题来了，d一定最小么？
回答是相当确定的，就是肯定不是最小的。原因也显而易见，就是最近点对可能出现在PL与PR的分割处。
④ 根据③中的问题，可以以part_line为中心左右|d|的距离里的点考虑（为什么？超过这个距离显然不需要 考虑啦，因为距离一定会大于d啦~~~）。现在，问题又来了，如何取得这个范围内的最近点呢？蛮力？全搜索计算？对！不行的这是，可能所有的点都落在这个范围里，就此一项我的时间复杂度就又会回到Q(n2)。怎么办？
⑤ 对于④中的问题，解决方法是这样的，将左右|d|范围里的点按Y值排序，然后依次从每个点出发做水平线，并在其之上d的距离做水平线，这样得到了一个2d*d的矩形，显然，在此矩形之外的点无需开率啦，可以证明，矩形内最多容下8个点（包括自己本身）。所以意味着在排好序的Y坐标点中，只需要考虑其后的7个点就行了，此外已有人证明了事实上只需要考虑其后的4个点就行啦。可见，这些的时间复杂度最多Q（N）。
⑥ 纵观整个过程，首先要对X坐标排序时间为O（NlogN），这是分治之前的预处理。然后问题分成了N/2规模，然后用Q（N）的复杂度得到中间的最近点对，然后可以在常数时间内得到最终的点对与最近值。So。。。T（N）=2T（N/2）+O（N），可以得到该算法的时间为O（NlogN）（即使加上一开始的排序预处理的时间复杂度）。
