接下来我将用三种不同的方法求解“平面最近点对”问题。
问题描述：在一个平面上随机分布着 n 个点，现给定 n 个点的坐标，要求给出最近的两个点之间的距离。
方法一：原始方法
题目要求求出最近的两点之间的距离，先整理一下已知的线索：首先点的总个数为 n ；其次已知 n 个点的坐标。掌握了每个点的坐标，就相当于间接地掌握了任意两点之间的距离。假设两个点为 A : ( x1 , y1 ) , B : ( x2 , y2 ) ,两点间的距离为 distance ，根据平面坐标系中的两点间距离公式可得：
distance ^ 2 ＝ ( x1 - x2 ) ^ 2 + ( y1 - y2 ) ^ 2，
运用该公式对每两个点的距离进行计算，并不断更新最小值 min_distance 。
这个方法很直观也最容易想到，不过，由以上的两层循环可知，该方法的时间复杂度为 o （ n ^ 2 ) ，当 n 的值不断增大时，这个方法处理起来就显得力不从心了。因此我们必须寻找另一种更有效的方法，或者在此方法上进行适当的改进。
接下来一起了解一下第二种方法－－分治法
方法二：分治法
为了做到有理有据，正式叙述解法之前，我得再啰嗦几句选择分治法的原因，希望不会引起大家的反感。在本问题中，需要求得最近两点之间的距离，整个问题的规模为 n 个点，不妨将这 n 个点一分为二，就变成两个求解 n ／2 个点规模下最近点对的距离问题， 如此不断缩小规模，当变成两个点的规模下求解最近点对问题时，显而易见，即为这两个点的距离，这样随着问题规模的缩小解决的难易程度逐渐降低的特征正是可以用分治法解答的问题所具备的特征。
接下来，我们按照分治法解题步骤 分割－－求解－－合并 分析这个问题。将n 个点分为两部分后，最近的两个点有可能出现在第一部分中，也有可能出现在第二部分中，当然还有可能一个在第一部分中，另一个在第二部分中，于是我们可以分别求出三种情况下最近点对的距离 dis1 dis2 dis3 ，从这三者中选择出最小的一个作为本规模下的解。
分割：将 n 个点分为两部分，每部分包含 n ／2 个点，
求解：分别对两部分按照同样的方法求得最近距离 dis1 和dis2 ，
合并：求解两点分别分布在两个部分的情况下的最近距离 dis3 ，取 dis1 dis2
dis3 三者中的最小者。
思路如上，我们再对具体的细节进行完善
如何求子规模下的最近距离？
我们可以使用递归调用的方法来实现子规模的求解，递归有终止条件，这个问题的递归终止条件应该是当规模为 2 时，最近点对的距离即为这两点的距离。
如何求合并后两点分属两个部分时的最近距离？
由于两点分属两个部分这种情况下，找寻任意一个点的范围都太过宽泛，因此我们需要使用技巧来缩小寻找范围。
这时候我们假设从两部分分别求出的最近距离为 dis1 和 dis2 ，
dis ＝ min（ dis1， dis2 ），再假设分属两部分的情况下，A ( x1 , y1 ) 属于第一部分 ,B ( x2 , y2 )属于第二部分，且以 x 轴作为分割的量，我们可以断定 如果存在解 ，A 、B 两点一定处在中心分割线两侧 2＊dis 长度之内的区间内，（考虑到极端情况下有一点处在分割线上的情况，因此不能选择 dis 长度区间），示意如下图：
中心分割线为 x ＝ mid ，ans ＝ dis ，那么，A 点一定存在于 x ＝ mid － ans 和 x ＝ mid 这两条直线之间的区域，同时， B 点一定存在于 x ＝ mid 和 x ＝ mid ＋ ans 这两条直线之间的区域。
这时候，只要在中轴线左右两侧分别不超过 dis 的距离范围内进行求解即可。
我们可以逐个枚举x = mid-dis 与 x=mid+dis 两条线之间所有点的两两距离。在处理之前我们可以做一些准备工作进一步优化求解过程。首先将所有点按照 y 坐标值升序进行排序，这样做有一个好处：当某一点 A的纵坐标 y1 与 某一点 B 的纵坐标 y2 满足 y2 － y1 > dis 时，可以直接断定当前的 A点与 纵坐标大于 y2 的任意一个点的距离都会超过 dis ，也就不用判断其余的点，省去了不少时间。
思路已经描述完毕，接下来为大家奉上本方法的核心代码。
下面给大家分享第三种方法。
方法三：分治法改进版
在完整介绍这种方法之前，我们先来了解一个知识
如上图所示，上图中有一个边长为 L *2L 的矩形，将该矩形等分成六个 1/2 L ＊2/3 L 的小矩形。假设在该区域内散布着若干个点，并且任意两点之间的距离不小于 L ，请试着确定一下最多可以分布几个点？
答案是 最多可以分布六个点，每个小矩形内最多可以分布一个点。
我们用反证法来证明一下这个结论：
假设 分布的点数多于六个
由假设可知，
必然存在一个甚至多个矩形内有多于一个点；
同时，处在同一块矩形区域内的两个点的最大距离 ma x_dis 不会超过对角线的长度。在 1/2 L ＊ 2/3L 的矩形中，对角线长度为
sqrt（ ( 1/2 L)^2 + ( 2/3 L )^2 ）= 5/6 L , max_dis <= 5/6 L < L ，即最大距离不超过 L ，这与题目的要求相违背，因此，点数不会超过 6 。
再看下面这张图片：
已知：
中心轴线将一块区域分成 1 区 和 2 区 两个区间长度均为 L 的区域；
1 区 和 2 区中散布着若干个点，并且在 1 区内部任意两点之间的距离大于 L ，2 区也是如此；
我们称 1 区内的点为 A ， 2 区中的点为 B ，A 、B 两点的极限位置可以在中心轴线 x ＝ mid 上，如上图；
我们需要求满足以上条件的 A、B 两点的最近距离是否存在小于 L 的情况。
由以上条件，我们可以推测 当 A ( x1 , y1 ) 点的位置确定的时候，B ( x2 , y2 ) 点可能位置也必然确定，
即 y2 >= y1 - L 且 y2 <= y1 + L ， x2 >= mid 且 x2 <= mid + L ,
换言之，在上图中，只要 1 区 的点处在 A 点所在的水平线上，那么 2 区 中点的可能位置一定在图中的矩形区域中，因此，对于 1 区中的每个点，在 2 区中最多需要判断 6 个点就可以下结论。
有了上面的知识铺垫，那我们可以利用以上知识进一步优化分治法求最近点对距离的方法，可以预见对第二种方法改进的地方发生在合并两个子集合时对两点不属于同一个子集合的处理上，现在的任务就是对于 1 区的任意一个点，求出对应 2 区范围内需要判断的数目不超过六个的点都有哪些。我们可以在找这六个点的时候先用横坐标限制范围，再用纵坐标限制范围。每求一个点，都确定一次 2 区乱序的点哪些在范围内和遍历所有点实现上是一样麻烦的，我们需要有突破。这时候如果能将 2 区所有的点按照纵坐标进行排序，那么我们只要求得上、下界就可以了。为了省事，一般只求得上、下界之一，并连续的判断6个点即可。
具体的实现思路是，建立两个点集，集合一按照横坐标 x 的升序进行排列，集合二按照 y 的升序进行排列，同一规模下利用集合一求出 1 区 和 2 区的区间长度 L ，再利用 L 将集合二中处在 1 区 和 2 区范围内的点按照之前在集合二中的顺序挑选出来。接着逐个枚举 1 区中的点，确定该点对应在 2 区中需要判断的六个点并给予精准的判断。
下面我将此方法的核心代码向大家展示，文字没有解释清楚的地方，希望代码部分能够补足。
struct point
{
int x;//横坐标
int y;//纵坐标
}p[1000];
vector<point> part_x,//按照 x 升序点集
part_y;//按照 y 升序点集
int compare_x( point a ,point b )//根据点的横坐标比大小
{
return a.x < b.x;
}
int compare_y(point a , point b )//根据点的纵坐标比大小
{
return a.y < b.y;
}
double calculate_dis(point a,point b)//计算两点间距离
{
return sqrt( (a.x - b.x)^2 + (a.y - b.y)^2 );
}
double min(double a ,double b)//求两个数中的较小者
{
return a<b?a:b;
}
int max(int a,int b)//求两个数中的较大者
{
return a>b?a:b;
}
//中心轴线为 mid_x，当前最小点对距离为 dis ，求两个按照 y 升序的点集合并处的最小点对距离，并更新 dis 值
//返回值为更新后的 dis 值。
//参数 left_part_y 为 按照 y 升序的左半点集
//参数 right_part_y 为 按照 y 升序的右半点集
double merge(vector<point>& left_part_y, vector<point> right_part_y , double dis,int mid_x)
{
vector<point> p1,//按照 y 升序存储 1 区的点
p2;//按照 y 升序存储 2 区的点
for(int i = 0 ; i < left_part_y.size() ; i ++)
{
if(left_part_y[i].x>=mid_x - dis)//将左半点集中处在 1 区的点存入p1
{
p1.push_back(left_part_y[i]);
}
}
for(int i = 0 ; i < right_part_y[i].size() ; i ++)
{
if(right_part_y[i].x <= mid_x + dis)//将右半点集中处在 2 区的点存入p2
{
p2.push_back(right_part_y[i]);
}
}
for(int i = 0 ; i < p1.size();i++)//对 1 区中的点逐个枚举
{
int j = 0;
while(p2[j].y<p1[i].y && j<p2.size()) j++;//找到 2 区中与 1 区当前枚举点纵坐标差的绝对值最小的点的索引
int begin,end;
begin = max(0,j-3);
if(j+3<p2.size()-1)
{
end = j+3;
}
else end = p2.size()-1;//实际上此处最多枚举了七个点
for( int k = begin;k<= end; k++)
{
dis = min(dis,calculate_dis(p1[i],p2[k]));
}
}
return dis;
}
//给定按照 x 升序的点集 part_x 和按照 y 升序的同一点集 part_y, 排序是为了合并处理时方便
//返回该点集中最近点对的距离
int min_distance(vector<point>& part_x , vector<point>& part_y )
{
vector<point> left_part_x,//存储 按照 x 升序的 part_x 点集的左半部分
right_part_x,//存储按照 x 升序的 part_x 点集的右半部分
left_part_y,//存储按照 y 升序的 part_y 点集的左半部分
right_part_y;//存储按照 y 升序的 part_y 点集的右半部分
int mid = part_x.size()/2;
for( int i = 0 ; i < part_x.size() ; i ++)
{
if(i <= mid )//将 part_x 点集左半部分存入left_part_x
{
left_part_x.push_back( part_x[i] );
}
else//将 part_x 点集右半部分存入right_part_x
{
right_part_x.push_back( part_x[i]);
}
if(part_y[i].x<=part_x[mid].x)//将 part_y 点集中属于 left_part_x 中的点存入 left_part_y
{
left_part_y.push_back( part_y[i]);
}
else//将 part_y 点集中属于right_part_x 的点存入 right_part_y
{
right_part_y.push_back( part_y[i]);
}
}
if(part_x.size() == 2 )//处理 part_x 中只有两个点的情况
{
return distance = calculate_dis(part_x[0],calculate_dis[1]);
}
//处理多余两个点的情况
double dis1 ,dis2,dis3,dis;
dis1 = min_distance(left_part_x ,left_part_y);//将左半区间点集递归处理
dis2 = min_distance(right_part_x,right_part_y);//将右半区间点集递归处理
dis = min(dis1,dis2);
dis = merge(left_part_y,right_part_y,dis,part_x[mid].x);//求合并处的最近点对距离并更新 dis 值
return dis;
}
```3