[POJ3714]Raid[分治,平面最近点对]

#include<cstdio>
#include<cmath>
#include<algorithm>
#define re register
#define in inline
#define db double
#define int long long
using namespace std;
in int read()
{
	int s(0),b(0);char ch;
	do{ch=getchar();if(ch=='-')b=1;}while(ch<'0'||ch>'9');
	while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
	if(b) return -s;
	return s;
}
struct P{int x,y,t;}p[200010];//t用来标记点是哪一类, 题目要求在两类点之间找最近点对
in bool cmpx(const P &a,const P &b){return a.x<b.x;}
in bool cmpy(const int &a,const int &b){return p[a].y<p[b].y;}
int n,ls[200010];
in db abss(db x){if(x>=0.0) return x;return -x;}//最好不要和STL里的abs重名, POJ上会CE
in db dis(int a,int b){return sqrt((db)(p[a].x-p[b].x)*(p[a].x-p[b].x)+(p[a].y-p[b].y)*(p[a].y-p[b].y));}//必须强制转换为double, 因为sqrt的参数和返回值都是double, 否则POJ上CE
db work(int l,int r)
{
	if(l>=r) return (db)1e20;
	if(l+1==r){
		if(p[l].t!=p[r].t) return dis(l,r);
		return (db)1e20;
	}
	int mid=(l+r)>>1,cnt=0;
	db ans=min(work(l,mid),work(mid+1,r));
	for(re int i=l;i<=r;++i)
		if(abss((db)p[i].x-(db)p[mid].x)<=ans) ls[++cnt]=i;
	sort(ls+1,ls+cnt+1,cmpy);
	for(re int i=1;i<=cnt;++i)
	{
		for(re int j=i+1;j<=cnt;++j)
		{
			if((db)p[ls[j]].y-(db)p[ls[i]].y>ans) break;//后面的点距离更大, 不可能成为答案了
			if(p[ls[i]].t!=p[ls[j]].t&&dis(ls[i],ls[j])<ans) ans=dis(ls[i],ls[j]);
		}
	}
	return ans;
}
signed main()
{
	int T=read();
	while(T--)
	{
		n=read();
		if(n==-1) break;
		for(re int i=1;i<=n;++i) p[i].x=read(),p[i].y=read(),p[i].t=1;
		for(re int i=n+1;i<=n+n;++i) p[i].x=read(),p[i].y=read(),p[i].t=2;
		n*=2;
		sort(p+1,p+n+1,cmpx);
		printf("%0.3lf\n",work(1,n));
	}
	return 0;
}