平面最近点对模板题。
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #define maxn 100500 #define inf 1e20 using namespace std; struct point { double x,y; }p[maxn]; int n,stack[maxn]; bool cmp(int a,int b) { return p[a].y<p[b].y; } bool cmpp(point a,point b) { if (a.x!=b.x) return a.x<b.x; return a.y<b.y; } double dis(int a,int b) { return sqrt((p[a].x-p[b].x)*(p[a].x-p[b].x)+(p[a].y-p[b].y)*(p[a].y-p[b].y)); } double mn(double x,double y) { if (x>y) return y; return x; } double find(int left,int right) { if (left==right) return inf; if (left+1==right) return dis(left,right); int mid=(left+right)>>1; double now=mn(find(left,mid),find(mid,right)); int top=0; for (int i=left;i<=right;i++) { if (fabs(p[i].x-p[mid].x)<=now) stack[++top]=i; } sort(stack+1,stack+top+1,cmp); for (int i=1;i<=top;i++) for (int j=i+1;j<=top && p[stack[j]].y-p[stack[i]].y<now;j++) { double then=dis(stack[i],stack[j]); now=mn(now,then); } return now; } void work() { for (int i=1;i<=n;i++) scanf("%lf%lf",&p[i].x,&p[i].y); sort(p+1,p+n+1,cmpp); printf("%.2lf ",find(1,n)/2); } int main() { while (scanf("%d",&n)==1) { if (n==0) break; else work(); } return 0; }