剛好課上學(xué)了平面最近點(diǎn)對(duì)的算法，回來實(shí)現(xiàn)以下，恩 ，分治的思想很重要。呵呵，又學(xué)會(huì)了一個(gè)算法。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
#define eps 1e-8
const int maxn=200001;
const double INF=999999999;
typedef struct point
{
double x,y;
//int flag;
point(){};
}point;
point p[maxn];
int n;
int cmp(double x,double y)
{
if(x==y)return 0;
if(x>y)return 1;
return -1;
}
bool cmp1(point a,point b)
{
if(a.x!=b.x)
return a.x<b.x;
else
return a.y<b.y;
}
bool cmp2(int i,int j)
{
return cmp(p[i].y,p[j].y)<0;
}
double dist(point &a,point &b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
int y[maxn],len;
double cp(point p[],int l,int r)//求從l到r這些點(diǎn)的最近點(diǎn)對(duì)
{
int i,j;
int mid=(l+r)>>1;
double ret=INF;
if(l>=r)
return ret;
for(i=mid;i>=l&&!cmp(p[i].x,p[mid].x);i--);
double t1=cp(p,l,i);
for(i=mid;i<=r&&!cmp(p[i].x,p[mid].x);i++);
double t2=cp(p,i,r);
if(t1<t2)
ret=t1;
else ret=t2;
len=0;
for(i=l;i<=r;i++)
{
if(fabs(p[i].x-p[mid].x)<ret)
y[++len]=i;
}
sort(y+1,y+len+1,cmp2);
for(i=1;i<=len;i++)
{
int cnt=1;
for(j=i+1;j<=len&&cnt<=7;j++)
{
ret=min(ret,dist(p[y[i]],p[y[j]]));
cnt++;
}
}
return ret;
}
bool check(int n)
{
int i;
for(i=2;i<=n;i++)
{
if(p[i].x==p[i-1].x&&p[i].y==p[i-1].y)
return true;
}
return false;
}
int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
if(n==0)
break;
int i;
for(i=1;i<=n;i++)
scanf("%lf%lf",&p[i].x,&p[i].y);
sort(p+1,p+n+1,cmp1);
if(check(n))
{
printf("0.00\n");
continue;
}
double ans=cp(p,1,n)/2;
printf("%.2lf\n",ans);
}
return 0;
}