解析：平面上的点分治，先递归得到左右子区间的最小值d，
再处理改区间，肯定不会考虑哪些距离已经大于d的点对，
对y坐标归并排序，然后从小到大开始枚举更新d，对于某个点，
x轴方向只用考虑[x-d,x+d](x是分的中轴线)，y轴方向只用考虑
[y-d,y](y是这个点的y值),因为d值一直在变小，所以这个矩形包
含的点数很少。
代码
#include<cstdio> #include<cstring> #include<string> #include<vector> #include<cmath> #include<algorithm> using namespace std; const double INF=1e9; const int maxn=10005; int N; struct Po { double x,y; Po(double x=0,double y=0):x(x),y(y){} }po[maxn],B[maxn]; bool cmp(const Po& a,const Po& b) { if(a.x!=b.x) return a.x<b.x; return a.y<b.y; } double dfs(int l,int r) { if(l>=r) return INF; int mid=(l+r)/2; double x=po[mid].x; double d=min(dfs(l,mid),dfs(mid+1,r)); //先处理左右子区间 int ls=l,rs=mid+1,k=l; while(ls<=mid&&rs<=r) //归并排序 { if(po[ls].y<=po[rs].y) B[k++]=po[ls++]; else B[k++]=po[rs++]; } while(ls<=mid) B[k++]=po[ls++]; while(rs<=r) B[k++]=po[rs++]; for(int i=l;i<=r;i++) po[i]=B[i]; int Size=0; for(int i=l;i<=r;i++) { if(fabs(po[i].x-x)>=d) continue; //不考虑 for(int j=Size;j>=1;j--) { double a=po[i].x-B[j].x; double b=po[i].y-B[j].y; if(b>=d) break; d=min(d,sqrt(a*a+b*b)); //更新 } B[++Size]=po[i]; } return d; } int main() { while(scanf("%d",&N)!=EOF&&N) { double x,y; for(int i=1;i<=N;i++) { scanf("%lf%lf",&x,&y); po[i]=Po(x,y); } sort(po+1,po+N+1,cmp); double ans=dfs(1,N); if(ans<10000) printf("%.4f ",ans); else printf("INFINITY "); } return 0; }