$Sol$
平面最近点对板子题,注意要求的是两种不同的点之间的距离.
$Code$
#include<bits/stdc++.h> #define il inline #define Rg register #define go(i,a,b) for(Rg int i=a;i<=b;++i) #define yes(i,a,b) for(Rg int i=a;i>=b;--i) #define mem(a,b) memset(a,b,sizeof(a)) #define ll long long #define db double #define inf 2100000000 using namespace std; il int read() { Rg int x=0,y=1;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')y=-1;c=getchar();} while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();} return x*y; } int T,n; struct node{int x,y;bool tp;}a[(int)1e5*2+1],tmp[(int)1e5*2+1]; il bool cmp(node x,node y){if(x.x==y.x)return x.y<y.y;return x.x<y.x;} il bool cmp1(node x,node y){return x.y<y.y;} il ll dis(node x,node y){db xx=x.x-y.x,yy=x.y-y.y;return xx*xx+yy*yy;} il ll sol(int l,int r) { if(l>r || l==r)return inf; if(l+1==r) { if(a[l].tp!=a[r].tp){return dis(a[l],a[r]);} else return inf; } Rg int mid=(l+r)>>1,ct=0; ll mins=min(sol(l,mid),sol(mid+1,r)); go(i,l,r){if((a[i].x-a[mid].x)*(a[i].x-a[mid].x)<=mins)tmp[++ct]=a[i];} sort(tmp+1,tmp+ct+1,cmp1); go(i,1,ct) go(j,i+1,ct) { if((tmp[j].y-tmp[i].y)*(tmp[j].y-tmp[i].y)>mins)break; if(tmp[i].tp!=tmp[j].tp)mins=min(mins,dis(tmp[i],tmp[j])); } return mins; } int main() { T=read(); while(T--) { n=read(); go(i,1,n)a[i]=(node){read(),read(),1}; go(i,1,n)a[i+n]=(node){read(),read(),0}; sort(a+1,a+n*2+1,cmp); printf("%.3lf ",sqrt(sol(1,2*n))); } return 0; }