编程之美：寻找最近点对

题目描述：

给定N个点坐标，找出距离最近的两个点。

解答：

采用分治的思想。

将坐标点按照x从小到大进行排序，对于x相同的点按照y从小到大排序

我这里只是针对左右边界进行限界，对上下边界没有限界，若出现横坐标相同的点个数较多的情况，复杂度相对较高了。

对于一般情况下，横坐标相同的情况不多时，时间复杂度可达到O(NlogN)

/*
寻找最近点对:

*/
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
#define N 5
#define INF 999999

struct NODE{
	int x;
	int y;
	bool operator<(const NODE &t){
		if(x==t.x)return y<t.y;
		return x<t.x;
	}
};
NODE node[N]={{0,0},{1,1},{1,3},{2,0},{3,2}};
double minDis = INF;

void solve(int s,int e){
	if(s>=e)return;

	int mid=(s+e)/2;

	solve(s,mid);
	solve(mid+1,e);

	int x=node[mid].x;
	int y=node[mid].y;
	int left=x-minDis;//左边界
	int right=x+minDis;//右边界
	//int up=y+minDis;//上边界
	//int down=y-minDis;//下边界
	int index=mid-1;
	while(index>=0&&left<node[index].x){
		int t=mid-1;
		while(t>=0&&node[t].x==node[mid-1].x){
			minDis=min(minDis,sqrt((double)(x-node[t].x)*(x-node[t].x)+(y-node[t].y)*(y-node[t].y)));
			t--;
		}
		left=x-minDis;
		index--;
	}
	index=mid+1;
	while(index<N&&right>node[index].x){
		int t=mid+1;
		while(t<N&&node[t].x==node[mid+1].x){
			minDis=min(minDis,sqrt((double)(x-node[t].x)*(x-node[t].x)+(y-node[t].y)*(y-node[t].y)));
			t++;
		}
		index++;
		right=x+minDis;
	}
}

int main()
{
	sort(node,node+N);
	solve(0,N-1);
	cout<<minDis;
	return 0;
}

编程之美：寻找最近点对,布布扣,bubuko.com

编程之美：寻找最近点对

原文：http://blog.csdn.net/starcuan/article/details/21289165