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

// Time 2093 ms; Memory 1812 K  

#include  
#include  
#include  
#include  
#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





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