HDU 1007 平面上最近点对 分治

思路：

分治

套路题

//By SiriusRen
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N=100050;
typedef double db;
int n;
struct P{db x,y;P(){}P(db X,db Y){x=X,y=Y;}}p[N],t[N];
P operator-(P a,P b){return P(a.x-b.x,a.y-b.y);}
db dis(P a){return sqrt(a.x*a.x+a.y*a.y);}
bool cmp(P a,P b){return a.x<b.x;}
bool cmp2(P a,P b){return a.y<b.y;}
db solve(int l,int r){
    if(l==r)return 1e9;
    int mid=(l+r)>>1,tp=0;
    db d=min(solve(l,mid),solve(mid+1,r));
    for(int i=l;i<=r;i++)if(p[i].x>=p[mid].x-d&&p[i].x<=p[mid].x+d)t[++tp]=p[i];
    sort(t+1,t+1+tp,cmp2);
    for(int i=1;i<=tp;i++){
        for(int j=i+1;j<=tp;j++){
            if(t[j].y>=t[i].y+d)break;
            d=min(d,dis(t[i]-t[j]));
        }
    }
    return d;
}
int main(){
    while(scanf("%d",&n)&&n){
        for(int i=1;i<=n;i++)scanf("%lf%lf",&p[i].x,&p[i].y);
        sort(p+1,p+1+n,cmp);
        printf("%.2lf
",solve(1,n)/2);
    }
}