poj 3714 Raid 分治法求平面最近点对

题意：

给平面上的n个点，求两点间的最短距离。

分析：

分治法，保存点用vector会tle...

代码：

//poj 3714
//sep9
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const double INF=1e50;
struct P
{
	double x,y;
	int type;
}p[240000],b[240000];

bool cmp_x(P a,P b)
{
	return a.x<b.x;
}

bool cmp_y(P a,P b)
{
	return a.y<b.y;
}

double closest_pair(P *a,int n)
{
	if(n<=1)
		return INF;	
	int m=n/2;
	double x=a[m].x;
	double d=min(closest_pair(a,m),closest_pair(a+m,n-m));
	inplace_merge(a,a+m,a+n,cmp_y);
	int yn=0;
	for(int i=0;i<n;++i){
		if(fabs(a[i].x-x)>=d)
			continue;
		for(int j=0;j<yn;++j){
			double dx=a[i].x-b[yn-1-j].x;
			double dy=a[i].y-b[yn-1-j].y;
			if(dy>=d)
				break;
			if(a[i].type==b[yn-1-j].type)
				continue;
			d=min(d,sqrt(dx*dx+dy*dy));
		}
		b[yn++]=a[i];	
	}
	return d;
}

int main()
{
	int cases;
	scanf("%d",&cases);
	while(cases--){
		int i,n;
		scanf("%d",&n);		
		for(i=0;i<n;++i){
			scanf("%lf%lf",&p[i].x,&p[i].y); 
			p[i].type=0;
		}
		for(i=n;i<2*n;++i){
			scanf("%lf%lf",&p[i].x,&p[i].y); 
			p[i].type=1;
		}
		n=2*n;
		sort(p,p+n,cmp_x);
		printf("%.3f\n",closest_pair(p,n)+1e-6);
	}
	return 0;	
} 

poj 3714 Raid 分治法求平面最近点对

原文：http://blog.csdn.net/sepnine/article/details/44158277