1.问题

最近点对问题：在一个平面上随机分布着 n 个点，现给定 n 个点的坐标，要求给出最近的两个点之间的距离。

2.解析

1.暴力算法：
在双重for暴力的情况下，该问题的时间复杂度为O(n²)，当 n 的值不断增大时，这个方法处理起来就显得效率很低。
2.分治法：
分治法的思想是将平面上的点分成左右两半，分别求左右两半的最小距离，然后取一个最小值，整个问题的规模为n个点，将这n个点一分为二，就变成两个求解n／2个点规模下最近点对的距离问题，如此不断缩小规模，当变成两个点的规模下求解最近点对问题时，即为这两个点的距离。当然，最近点对还可能会有这样的情况，即一个点在左半边，一个点在右半边。

分解：
对所有的点按照x坐标从小到大排序（排序方法时间复杂度O(nlogn)）。
根据下标进行分割，使得点集分为两个集合。
解决：
递归的寻找两个集合中的最近点对。
取两个集合最近点对中的最小值dis。
合并：
最近距离不一定存在于两个集合中，可能一个点在集合A，一个点在集合B，而这两点	间距离小于dis。
其中合并的这一步具体展开：
我们假设从两部分分别求出的最近距离为 dis1 和 dis2 ， dis ＝ min（ dis1， dis2 ），再假设分属两部分的情况下，A ( x1 , y1 ) 属于第一部分 ,B ( x2 , y2 )属于第二部分，且以 x 轴作为分割的量，我们可以断定，如果存在解，A 、B 两点一定处在中心分割线两侧 2＊dis 长度之内的区间内，且经过相关证明，在这范围内的点不会超过6个。

3.设计

float closest(Point* points, int n, Point& a, Point& b) {
	//递归函数出口,两个点直接返回距离,一个点时返回无穷大
	if (n == 2) 
		return distance(a, b);
	else if (n == 1) {
		return INF;
	}
	else {//分治
		int n1 = n / 2;//前一半
		int n2 = n - n1;//后一半
		//左右两个分区 分别存入points1和points2
		for (遍历左半边) 
			points1[i] = points[i];
		for (遍历右半边) 
			points2[i] = points[i + n1];
		d1 = closest(points1, n1, a1, b1);//递归得到左半边最小距离d1
		d2 = closest(points2, n2, a2, b2);//递归得到右半边最小距离d2
			dis = min(d1, d2);
		//中间区域
		for (遍历1到n) {
			if (fabs(points[i].x - mid) <= dis) {//若到中轴距离小于dis
				points3[++k] = points[i];//存入points3
			}
		}
		for (遍历1到k) {
			for (最多遍历6个点) {
				if (distance(points3[i], points3[j]) < dis) {
					dis = distance(a, b);
				}
			}
		}
		return dis;
	}
}

4.分析

快排的时间为O(nlogn)，而遍历的时间小于O(nlogn)，于是计算后得到整体时间复杂度为O(nlogn)。