题目：POJ 3714 Raid

代码：

#include <cstdio>
#include <cmath>
#include <algorithm>
#define INF 1e66
#define int long long
using namespace std;
const int N=200377;
int t,n,nn;
struct P{
	double x,y;
	int t;
}p[N];
inline int cmp1(const P &a,const P &b){
	if(a.x==b.x) return a.y<b.y;
	return a.x<b.x;
}
inline int cmp2(const P &a,const P &b){
	return a.y<b.y;
}
inline double dis(const P &a,const P &b){
	double dx=a.x-b.x,dy=a.y-b.y;
	return sqrt(dx*dx+dy*dy);
}
double getans(int l,int r){
	static P pt[N];
	static int cnt=0;
	if(l==r){
		return INF;
	}
	if(r==l+1){
		if(p[l].t^p[r].t){
			return dis(p[l],p[r]);
		}
		return INF;
	}
	int mid=(l+r)>>1;
	double d,d1=getans(l,mid),d2=getans(mid+1,r);
	d=min(d1,d2);
	cnt=0;
	for(register int i=l;i<=r;++i){
		if(fabs(p[i].x-p[mid].x)<d){
			pt[++cnt]=p[i];
		}
	}
	sort(pt+1,pt+cnt+1,cmp2);
	for(register int i=1;i<=cnt;++i){
		for(register int j=i+1;j<=cnt&&pt[j].y-pt[i].y<d;++j){
			if(pt[i].t^pt[j].t){
				d=min(d,dis(pt[i],pt[j]));
			}
		}
	}
	return d;
}
signed main(){
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n);
		nn=n<<1;
		for(register int i=1;i<=n;++i){
			scanf("%lf%lf",&p[i].x,&p[i].y);
			p[i].t=0;
		}
		for(register int i=n+1;i<=nn;++i){
			scanf("%lf%lf",&p[i].x,&p[i].y);
			p[i].t=1;
		}
		sort(p+1,p+nn+1,cmp1);
		printf("%.3lf\n",getans(1,nn));
	}
	return 0;
}