编程之美-2.11 寻找最近点对

问题描述：给定平面上N个点的坐标，找出距离最近的两个点。

解决方法：参考编程之美书上所介绍的解法三（分治思想）。

方法框架：    1. 将点按照x坐标排序，找到中间点M将所有点分成两个部分，Left和Right。

2. 找出Left和Right区域分别最小的两点距离DisL, DisR, 则最短距离为DisMin=Min(DisL, DisR);

3. 在所有节点中找到x属于(M.x-DisMin, M.x+DisMin)的点，然后将这些点（设P表示这个点集）按y坐标排序，找这些点中两点之间距离<DisMin的点对。这里对于点a, 有可能与a的距离小于DisMin的点只能在矩形S里阴影里，如下图所示，由抽屉原理，与a有可能距离小于DisMin的点也只能是在a.y最近的6个点中，原理可证与第七个点及其他点距离一定大于DisMin。

4. 将P中的点依次找最近的6个点（有可能不够6个），然后判断距离是否小于DisMin，若小于则更新DisMin，否则继续，直到P中的点全部遍历结束。

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#define pointNumMax 6
using namespace std;
const double INF = 1e20;

struct Point
{
	double x;
	double y;
};

bool cmpxy(const Point &a, const Point &b){
	if (a.x != b.x)
		return a.x < b.x;
	return a.y < b.y;
}

bool cmpy(const Point &a, const Point &b){
	return a.y < b.y;
}

double min(double a, double b)
{
	return a < b ? a : b;
}

double dis(const Point &a, const Point &b){
	return sqrt((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y));
}

double minDisPair(Point* p, int left, int right)
{
	double d = INF;
	if (left == right)
		return d;
	if (left + 1 == right)
		return dis(p[left], p[right]);
	int mid = (left + right) >> 1;
	double d1 = minDisPair(p, left, mid);
	double d2 = minDisPair(p, mid+1, right);
	double minDis = min(d1, d2);
	int i, j;
	vector<Point> tmp;
	for (i = left; i <= right; i++)
	{
		if (fabs(p[i].x - p[mid].x) < minDis)
			tmp.push_back(p[i]);
	}
	sort(tmp.begin(), tmp.end(), cmpy);
	int len = tmp.size();
	for (i = 0; i < len-1; i++)
	{	
		for (j = i + 1; (j < len)&&(j <= pointNumMax + i)  && ((tmp[j].y - tmp[i].y) < minDis) ; j++)
		{
			double tmpDis = dis(tmp[j], tmp[i]);
			if (tmpDis < minDis)
				minDis = tmpDis;
		}
	}
	return minDis;
}

int main()
{
	int n = 3;
	Point* point = new Point[n];
	for (int i = 0; i < n; i++)
		scanf("%lf %lf", &point[i].x, &point[i].y);
	sort(point, point + n, cmpxy);
	printf("%.2lf\n", minDisPair(point, 0, n - 1));		
	return 0;
}
           

这里参考了如下两边博客文章：

http://blog.csdn.net/hysfwjr/article/details/8916478

http://blog.csdn.net/lu1012123053/article/details/9825175