程式設計之美-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