hdu 1007 Quoit Design(分治法求最近点对)

// Time 2093 ms; Memory 1812 K  

#include<iostream>  
#include<cstdio>  
#include<cmath>  
#include<algorithm>  
#define eps 1e-8  
#define maxn 100010  
#define sqr(a) ((a)*(a))  
  
using namespace std;  
  
int sig(double x)  
{  
    return (x>eps)-(x<-eps);  
}  
  
struct point  
{  
    double x,y;  
    point(double xx=0,double yy=0):x(xx),y(yy){}  
}p[maxn];  
  
bool operator < (point a,point b)  
{  
    return a.x<b.x || (a.x==b.x && a.y<b.y);  
}  
bool cmp(point a,point b)  
{  
    return a.y<b.y || (a.y==b.y && a.x<b.x);  
}  
double len(point a,point b)  
{  
    return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y));  
}  
double min_dis(int l,int r)  
{  
    int i,j,k,s;  
    double d,mi=-1;  
    if(r-l<4)  
    {  
        for(i=l;i<r;i++) for(j=i+1;j<r;j++)  
        {  
            d=len(p[i],p[j]);  
            if(mi<0 || sig(d-mi)<0) mi=d;  
        }  
        return mi;  
    }  
    int mid=(l+r)/2;  
    double minl=min_dis(l,mid);  
    double minr=min_dis(mid,r);  
    mi=minl<minr?minl:minr;  
    for(i=1;i<mid-l && sig(p[mid].x-p[mid-i].x-mi)<0;i++);i--;  
    for(j=1;j<r-mid && sig(p[mid+j].x-p[mid].x-mi)<0;j++);j--;  
    sort(p+mid-i,p+mid,cmp);  
    sort(p+mid,p+mid+j+1,cmp);  
    int t=mid,flag;  
    for(k=mid-i;k<mid;k++)   
    {  
        flag=1;  
        for(s=t;s<=mid+j;s++)  
        {  
            if(sig(p[k].y-p[s].y)>0)  
            {  
                if(sig(p[k].y-p[s].y-mi)>=0) continue;  
                else  
                {  
                    if(flag)  
                    {  
                        flag=0;t=s;  
                    }  
                    d=len(p[s],p[k]);  
                    if(sig(d-mi)<0) mi=d;  
                }  
            }  
            else  
            {  
                if(sig(p[s].y-p[k].y-mi)>=0) break;  
                else  
                {  
                    d=len(p[s],p[k]);  
                    if(sig(d-mi)<0) mi=d;  
                }  
            }  
        }  
    }  
    sort(p+mid-i,p+mid+j+1);  
    return mi;  
}  
  
int main()  
{  
    int i,n;  
    while(scanf("%d",&n)!=EOF && n)  
    {  
        for(i=0;i<n;i++) scanf("%lf%lf",&p[i].x,&p[i].y);  
        sort(p,p+n);  
        printf("%.2lf\n",min_dis(0,n)/2);  
    }  
    return 0;  
}