poj3714——Raid

题意：给定两组坐标，求两组之间的最小距离。

思路：即最近点对。

参考算法导论，

http://blog.csdn.net/jw72jw/archive/2011/01/22/6158679.aspx

http://blog.csdn.net/smsmn/archive/2010/10/25/5963487.aspx

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
#define maxn 200005
#define maxcost 1e100
class point 
{
public:
	double x,y;
	int flag;
};
point p[maxn];
bool cmp1(point a,point b)
{
	if(a.x<b.x ||a.x==b.x&&a.y<b.y)return true;
	return false;
}
double dist(point a,point b)
{
	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
double min_dis(int l,int r)
{
	int i,j;
	double resultl =0,resultr=0,minlen=maxcost;
	if(r>l+2)
	{
		int mid=(l+r)>>1;
		double tempdis=maxcost;
		resultl=min_dis(l,mid);
		resultr=min_dis(mid,r);
		minlen=resultl<resultr?resultl:resultr;
		for(i=mid;i>=l&&p[i].x >p[mid].x-minlen;i--)
		{
			for(j=mid;j<=r&&p[j].x<p[mid].x+minlen;j++)
			{
				if(p[i].flag !=p[j].flag )
					tempdis=dist(p[i],p[j]);
				if(tempdis<minlen)
					minlen=tempdis;
			}
		}
	}
	else  
	{
		double dis;
		for(i=l;i<r;i++)
			for(j=1+i;j<=r;j++)
			{
				if(j==i) continue;
				if(p[i].flag !=p[j].flag )
				{
					dis=dist(p[i],p[j]);
					minlen=minlen<dis?minlen:dis;
				}
			}
	}
	return minlen; 
}
int main()
{
	int n,ca;
	cin>>ca;
	while(ca--)
	{
		cin>>n;
		for(int i=1;i<=n;i++)
		{	scanf("%lf%lf",&p[i].x,&p[i].y); p[i].flag =1;}
		for(int i=1+n;i<=n*2;i++)
		{   scanf("%lf%lf",&p[i].x,&p[i].y); p[i].flag =2;}
		n*=2;
		sort(p+1,p+n+1,cmp1);
		double result=min_dis(1,n);
		printf("%.3f\n",result);
	}
	return  0;
}