【HDU1007】Quoit Design（分治求平面最近点对）

假设当前区间为[l,r] 中间点为mid

那么最近点对 要么在[1,l]中，要么在[l+1,r]中，要么两边各有一个

我们递归处理出左区间的 最近点对距离d1 右区间d2 取d=min(d1,d2)

然后有两个剪枝来处理情况3

1.按x为关键字排个序，枚举[l,r]的点，假如一个点的x与中间点的x差值已经超过了d，那肯定不满足要求，因为还要算上y

2.剪枝1还不够，当我们已经筛选出符合剪枝1的点后，把这些点又按照y为关键字排个序，同样的，假如一个点的y与当前点的x差值已经超过了d，那他之后的点都是不满足要求的，可以break掉，然后顺便统计答案

#include<bits/stdc++.h>
#define N 100005
using namespace std;
struct Node
{
    double x,y;
}p[N];
int n;
inline bool cmp1(const Node &a,const Node &b)
{
    if(a.x==b.x)    return a.y<b.y;
    return a.x<b.x;
}
inline bool cmp2(const int &a,const int &b)
{
    return p[a].y<p[b].y;
}
double dis(Node a,Node b)
{
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
int temp[N];
double solve(int l,int r)
{
    if(l+1==r)  return dis(p[l],p[r]);
    if(l+2==r)  return min(dis(p[l],p[r]),min(dis(p[l+1],p[r]),dis(p[l],p[l+1])));
    int mid=(l+r)>>1;
    double d=min(solve(l,mid),solve(mid+1,r));
    int cnt=0;
    for(int i=l;i<=r;i++)
    {
        if(p[i].x>=p[mid].x-d&&p[mid].x+d>=p[i].x)
            temp[++cnt]=i;
    }
    sort(temp+1,temp+cnt+1,cmp2);
    for(int i=1;i<=cnt;i++)
    {
        for(int j=i+1;j<=cnt;j++)
        {
            if(p[temp[j]].y-p[temp[i]].y>=d)    break;
            d=min(d,dis(p[temp[i]],p[temp[j]]));
        } 
    }
    return d;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL),cout.tie(NULL);
    while(cin>>n&&n)
    {
        for(int i=1;i<=n;i++)   cin>>p[i].x>>p[i].y;
        sort(p+1,p+n+1,cmp1);
        cout<<fixed<<setprecision(2)<<solve(1,n)/2<<'\n';
    }
    return 0;
}