#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;
}
最新评论