模板题,不解释。
#include<stdio.h> #include<string.h> #include<stdlib.h> #include<algorithm> #include<math.h> using namespace std; const double eps = 1e-8; const int maxn = 100005; const double inf = 9999999999.0; struct Point { double x,y; }; struct Line{ Point a,b; }; Point pnt[ maxn ],temp[ maxn ]; 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 ) return dis( pnt[L],pnt[R] ); int mid = (L+R)/2; double Ldis,Rdis; Ldis=solve( L,mid ); Rdis=solve( mid+1,R ); double 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]; } }//分离出宽度为RES的点 sort( temp,temp+cnt,cmpy ); for( int i=0;i<cnt;i++ ){ for( int j=i+1;j<cnt;j++ ){ if( fabs(temp[i].y-temp[j].y)>res ) break; res = min( res,dis(temp[i],temp[j]) ); } } return res; } int main(){ int n; while( scanf("%d",&n),n ){ for( int i=0;i<n;i++ ) scanf("%lf%lf",&pnt[i].x,&pnt[i].y); sort( pnt,pnt+n,cmpxy ); double Ans = solve( 0,n-1 ); printf("%.2lf\n",Ans/2.0); } return 0; }