平面最近点对板子, 一个有趣的分治

还挺好写的...

#include 
    
     #include 
     
      #include 
      
       #include 
       
        using namespace std;const int maxn=100005;typedef pair
        
          pd;pd A[maxn];pd B[maxn];pd C1[maxn],C2[maxn];double sqr(double x){return x*x;}double dis(pd a, pd b){    return sqrt(sqr(a.first-b.first)+sqr(a.second-b.second));}double solve(int l, int r){    if(l==r)return 1e20;    int mid=(l+r)/2;    double midx=(A[mid].first+A[mid+1].first)/2;    double a1=solve(l,mid);    double a2=solve(mid+1,r);    double ans=min(a1,a2);    int k1=0,k2=0;    for(int i=l;i<=mid;++i){        if(A[i].first+ans>=midx)C1[++k1]=A[i];    }    for(int i=mid+1;i<=r;++i){        if(A[i].first-ans<=midx)C2[++k2]=A[i];    }    for(int i=1,L=1,R=0;i<=k1;++i){        while(R
         
          =C2[R+1].second)++R; while(L<=k2&&C1[i].second-ans>C2[L].second)++L; for(int j=L;j<=R;++j){ ans = min(ans, dis(C1[i],C2[j])); } } for(int i=l,j=mid+1;i<=mid||j<=r;(j>r||(i<=mid&&A[i].second<=A[j].second))?(i++):(j++)){ B[i+j-mid-1]=(j>r||(i<=mid&&A[i].second<=A[j].second))?(A[i]):(A[j]); } for(int i=l;i<=r;++i)A[i]=B[i]; return ans;}int main(){ int n; while(scanf("%d",&n),n!=0){ for(int i=1;i<=n;++i){ scanf("%lf%lf",&A[i].first,&A[i].second); } sort(A+1,A+n+1); printf("%.2f\n",solve(1,n)/2.0); } return 0;}