ZOJ2107 给定10^5个点，求距离最近的点对的距离。 O（n^2）的算法是显而易见的。
可以通过分治优化到O（nlogn）
代码很简单
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std; const double eps=1e-9; int cmp(double x)
{
if(fabs(x)<eps)return 0;
if(x>0)return 1;
else return -1;
} const double pi=acos(-1.0); inline double sqr(double x)
{
return x*x;
} struct point
{
double x,y;
point (){}
point (double a,double b):x(a),y(b){}
void input()
{
scanf("%lf%lf",&x,&y);
}
friend point operator +(const point &a,const point &b)
{
return point(a.x+b.x,a.y+b.y);
}
friend point operator -(const point &a,const point &b)
{
return point(a.x-b.x,a.y-b.y);
}
friend bool operator ==(const point &a,const point &b)
{
return cmp(a.x-b.x)==0&&cmp(a.y-b.y)==0;
}
friend point operator *(const point &a,const double &b)
{
return point(a.x*b,a.y*b);
}
friend point operator*(const double &a,const point &b)
{
return point(a*b.x,a*b.y);
}
friend point operator /(const point &a,const double &b)
{
return point(a.x/b,a.y/b);
}
double norm()
{
return sqrt(sqr(x)+sqr(y));
}
}; const int maxn=100000+10;
point a[maxn];
int n,s[maxn];
bool cmpx(int i,int j)
{
return cmp(a[i].x-a[j].x)<0;
} bool cmpy(int i,int j)
{
return cmp(a[i].y-a[j].y)<0;
} double min_dist(point a[],int s[],int l,int r)
{
double ans=1e100;
if(r-l<20)
{
for(int q=l;q<r;q++)
for(int w=q+1;w<r;w++)ans=min(ans,(a[s[q]]-a[s[w]]).norm());
return ans;
}
int tl,tr,m=(l+r)/2;
ans=min(min_dist(a,s,l,m),min_dist(a,s,m,r));
for(tl=l;a[s[tl]].x<a[s[m]].x-ans;tl++);
for(tr=r-1;a[s[tr]].x>a[s[m]].x+ans;tr--);
sort(s+tl,s+tr,cmpy);
for(int q=tl;q<tr;q++)
for(int w=q+1;w<min(tr,q+5);w++)
ans=min(ans,(a[s[q]]-a[s[w]]).norm());
sort(s+tl,s+tr,cmpx);
return ans;
} double Min_Dist(point a[],int s[],int n)
{
for(int i=0;i<n;++i)s[i]=i;
sort(s,s+n,cmpx);
return min_dist(a,s,0,n);
} int main()
{freopen("t.txt","r",stdin);
int n;
while(scanf("%d",&n)&&n!=0)
{
for(int i=0;i<n;i++)
a[i].input();
printf("%.2lf\n",Min_Dist(a,s,n)/2.);
}
return 0;
}