分治——最近点对

分而治之，一般是nlogn的复杂度，所以用分治来求最近点对

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>

#define INF 0x3f3f3f3f
using namespace std;
struct node{
    double x,y;
};


node co[100100];
node co1[100100];
int N;
double distance(int i,int j,node co[]){
    return sqrt(  (co[i].x-co[j].x)*(co[i].x-co[j].x)+(co[i].y-co[j].y)*(co[i].y-co[j].y)  );
}

int cmpy(node a,node b){
    return a.y<b.y;
}

int cmp(node a,node b){
    if(abs(a.x-b.x)<10e-5)
        return a.y<b.y;
    return a.x<b.x;
}

double division(int l,int r,node co[]){
    if(l==r) return INF;     //同一个点，距离无穷
    if(r-l==1){
        return distance(r,l,co);
    }
    int mid=(l+r)/2;
    double short1,short2;
    short1=division(l,mid,co);   //找左边的最短
    short2=division(mid,r,co);        //找右边的最短

    double shortest=min(short1,short2); 
    int pos=0;                              //找在shortest之间的点
    for(int i=l;i<=r;i++){
        if(abs(co[i].y-co[mid].y) < shortest ) co1[pos++]=co[i];
    }
    sort(co1,co1+pos,cmp);

    for(int i=0;i<pos-1;i++){     //这里主要是鸽巢定理保证其复杂度不高
        for(int j=i+1;j<pos;j++){
            shortest=min(distance(i,j,co1),shortest);
        }
    }
    return shortest;
}

int main(){
    while(scanf("%d",&N)&&N){
        for(int i=0;i<N;i++){
            scanf("%lf%lf",&co[i].x,&co[i].y);
        }
        sort(co,co+N,cmpy);
        double short1=division(0,N-1,co);
        printf("%.2lf
",short1/2);
    }
}