平面最近点对，以后再也不用vector了！会t。。。
#include<iostream> #include<algorithm> #include<vector> #include<cmath> using namespace std; const int N=200010; const double inf=2147483647; struct node{double x,y;bool k;}a[N],p[N],v[N]; bool cmp(const node&a,const node&b){return a.x<b.x;} double solve(int l,int r){ if(l>=r)return inf; int mid=(l+r)>>1; double ret=min(solve(l,mid-1),solve(mid+1,r)),d=a[mid].x; int t1=l,t2=mid+1; for(int i=l;i<=r;++i){ if(t2>r||t1<=mid&&a[t1].y<a[t2].y)p[i]=a[t1],++t1; else p[i]=a[t2],++t2; } int cnt=0; for(int i=l;i<=r;++i){ if(fabs(a[i].x-d)>=ret)continue; for(int j=cnt;j>=1;--j){ if(fabs(a[i].y-v[j].y)>=ret)break; if(a[i].k==v[j].k)continue; double x1=a[i].x,y1=a[i].y,x2=v[j].x,y2=v[j].y; ret=min(ret,sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2))); } v[++cnt]=a[i]; } return ret; } int main(){ int T; scanf("%d",&T); while(T--){ int n; scanf("%d",&n); for(int i=1;i<=n;++i){ scanf("%lf%lf",&a[i].x,&a[i].y); a[i].k=0; } for(int i=1;i<=n;++i){ scanf("%lf%lf",&a[i+n].x,&a[i+n].y); a[i+n].k=1; } sort(a+1,a+1+2*n,cmp); printf("%.3lf ",solve(1,2*n)); } return 0; }