只需要特判标记即可
#include<stdio.h> #include<string.h> #include<stdlib.h> #include<math.h> #include<algorithm> using namespace std; const double eps = 1e-8; const double inf = 9999999999.0; const int maxn = 100005; struct Point{ double x,y; int flag; }; Point pnt[ maxn<<1 ],temp[ maxn<<1 ]; double dis( Point a,Point b ){ return sqrt( (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y) ); } int cmpxy( Point a,Point b ){ if( a.x!=b.x ) return a.x<b.x; else return a.y<b.y; } int cmpx( Point a,Point b ){ return a.x<b.x; } int cmpy( Point a,Point b ){ return a.y<b.y; } double solve( int L,int R ){ if( L==R ) return inf; if( L+1==R ){ if( pnt[L].flag==pnt[R].flag ) return inf; else return dis( pnt[L],pnt[R] ); } int mid = (L+R)/2; double res,Ldis,Rdis; Ldis = solve( L,mid ); Rdis = solve( mid+1,R ); res = min( Ldis,Rdis ); int cnt = 0; for( int i=L;i<=R;i++ ){ if( fabs(pnt[i].x-pnt[mid].x)<=res ){ temp[cnt++] = pnt[i]; } } sort( temp,temp+cnt,cmpy ); for( int i=0;i<cnt;i++ ){ for( int j=i+1;j<cnt;j++ ){ if( fabs( pnt[i].y-pnt[j].y )>res ) break; if( pnt[i].flag==pnt[j].flag ) continue; res = min( res,dis(pnt[i],pnt[j]) ); } } return res; } int main(){ int ca; scanf("%d",&ca); while( ca-- ){ int n; scanf("%d",&n); for( int i=0;i<n;i++ ){ scanf("%lf%lf",&pnt[i].x,&pnt[i].y); pnt[i].flag = 1; } for( int i=n;i<2*n;i++ ){ scanf("%lf%lf",&pnt[i].x,&pnt[i].y); pnt[i].flag = 2; } sort( pnt,pnt+2*n,cmpxy ); double Ans = solve( 0,2*n-1 ); printf("%.3lf\n",Ans); } return 0; }