hdu 1007 Quoit Design（平面最近点对）

题意：求平面最近点对之间的距离

解：首先可以想到枚举的方法，枚举i，枚举j算点i和点j之间的距离，时间复杂度O（n）.

　　如果采用分治的思想，如果我们知道左半边点对答案d1，和右半边点的答案d2，如何求跨两边点之间的答案呢？显然只用枚举中线两边d=min（d1，d2）范围的点，并且每个点都只需要枚举上下范围在d以内的点，显然这样的点不会很多。

#include <algorithm>

#include <iostream>

#include <cstring>

#include <cstdio>

#include <vector>

#include <cmath>

#include <queue>

#include <deque>

#include <map>

using namespace std;

typedef long long ll;

const double inf=1e20;

const int maxn=;

struct Point{

    double x, y;

}point[maxn];

int n, mpt[maxn];

//以x为基准排序

bool cmpxy(const Point &a,const Point &b){

    if(a.x!=b.x)

        return a.x<b.x;

    return a.y<b.y;

}

bool cmpy(const int &a,const int &b){

    return point[a].y<point[b].y;

}

double min(double a,double b){

    return a<b?a:b;

}

double dis(int i,int j){

    return sqrt((point[i].x-point[j].x)*(point[i].x-point[j].x) + (point[i].y - point[j].y)*(point[i].y - point[j].y));

}

double Closest_Pair(int left, int right){

    double d=inf;

    if(left==right)

        return d;

    if(left+==right)

        return dis(left,right);

    int mid=(left+right)>>;

    double d1=Closest_Pair(left,mid);

    double d2=Closest_Pair(mid+,right);

    d=min(d1,d2);

    int i,j,k=;

    //分离出宽度为d的区间

    for(i=left;i<=right;i++){

        if(fabs(point[mid].x-point[i].x)<=d)

            mpt[k++]=i;

    }

    sort(mpt,mpt+k,cmpy);

    //线性扫描

    for(i=;i<k;i++){

        for(j=i+;j<k&&point[mpt[j]].y-point[mpt[i]].y<d; j++){

            double d3=dis(mpt[i],mpt[j]);

            if(d>d3)d=d3;

        }

    }

    return d;

}

int main(){

    while(scanf("%d",&n)!=EOF){

        if(n==)break;

        for(int i=;i<n;i++)

            scanf("%lf%lf",&point[i].x,&point[i].y);

        sort(point,point+n,cmpxy);

        printf("%.2lf\n",Closest_Pair(,n-)/);

    }

    return ;

}