poj3714 两个阵营的 平面最近点对
//poj3714 平面最近点对，基础见poj1007

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

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

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

#include<iostream>#include<cstdio>#include<stdlib.h>#include<math.h>#include<algorithm>#define eps 1e-8#define INF 1e12struct 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;}