poj3714 两个阵营的 平面最近点对

//poj3714 平面最近点对，基础见poj1007

//题目意思：有两个阵营，求一阵营的一点到另一个阵营的一个点存在的最小距离，

//注意给每个点添加相应的的阵营，在判断是否不同阵营时异或可得。

//代码如下：1688ms 有点久

#include<iostream>
#include<cstdio>
#include<stdlib.h>
#include<math.h>
#include<algorithm>
#define eps 1e-8
#define INF 1e12


struct Point 
{ double x,y;
int flag;
};
int  n;
Point px[200002],py[200002];
int temp[200002];

int cmpx(Point &a,Point &b)
{
    return a.x<b.x;
}
int cmpy(Point &a,Point &b)
{
    return a.y<b.y;
}
double Min(double a, double b) 
{  
    return a < b ?a : b;  
}  
double distance(Point a,Point b)
{
	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

double nearPair(int left,int right)
{
	double dis=INF;
	if(left+1==right)
		return (px[left].flag)^(px[right].flag)==1 ? distance(px[left],px[right]):INF;
	int i,j,cnt,mid;
	if(left+2==right)
	{
		for(i=left;i<=right;i++)
		{
			for(j=i+1;j<=right;j++)
			{
				if(px[i].flag ^ px[j].flag==1)
					dis=Min(dis,distance(px[i],px[j]));
			}
		}
		return dis;
	}
	mid=(left+right)>>1;
	dis=Min(nearPair(left,mid),nearPair(mid+1,right));
	for(i=left,cnt=0;i<=right;i++)
	{
		if(fabs(px[i].x-px[mid].x)<=dis)
		{
			py[cnt++]=px[i];
		}
	}
	std::sort(py,py+cnt,cmpy);
	for(i=0;i<cnt;i++)
	{
		for(j=i+1;j<cnt;j++)
		{
			if(py[i].flag^py[j].flag==1 && py[j].y-py[i].y>=dis)
                break;
            if(py[i].flag^py[j].flag==1)
				dis=Min(dis,distance(py[i],py[j]));
		}
	}
	return dis;
}

int main()
{
	int cas;
	scanf("%d",&cas);
	while(cas--)
	{scanf("%d",&n);
	int i;
	for(i=0;i<n;i++)
	{
		scanf("%lf%lf",&px[i].x,&px[i].y);
		px[i].flag=0;
		
	}
	for(i=n;i<2*n;i++)
	{
		scanf("%lf%lf",&px[i].x,&px[i].y);
		px[i].flag=1;
		
	}
	
	std::sort(px,px+2*n,cmpx);
	printf("%.3lf\n",nearPair(0,2*n-1));
	}
	return 0;
}