求散点最近点对（分治）

散点最近点对： 给一堆二维点，求两个点距离的最小值。

求解： 把点按x排序，取x值的中值x=xmid，以x=xmid为中线分割点，分别求左边和右边的最小距离，最后再找有没有两个点分属于左右子集，距离小于左子集和右子集的最小距离。当前集的最小距离为这3个值中的一个。一直左右分治到只剩两个点。

P1429 平面最近点对

#include<bits/stdc++.h>
#define ll long long
#define IOS std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define Rep(i,l,r) for(int i=(l);i<=(r);i++)
using namespace std;

struct Point{double x,y;};
Point operator-(const Point& a, const Point& b) {return (Point){a.x - b.x, a.y - b.y};}
double Dot(Point A, Point B){return A.x*B.x + A.y*B.y;}
double Length(Point A){return sqrt(Dot(A, A));}

int t,n;
Point a[1000005];
int b[2000005];

double dfs(int l,int r)
{
    double d = 1e20;
    if(l==r)return d;
    if(l+1==r)return Length(a[l]-a[r]);
    int mid = (l+r)/2;
    double d1=dfs(mid,r);
    double d2=dfs(l,mid-1);
    double mind=min(d1,d2);
    int k=0;
    Rep(i,l,r){
        if(abs(a[mid].x-a[i].x)<=mind){
            b[++k]=i;
        }
    }
    sort(b+1,b+1+k,[=](int ia,int ib)->bool{
        return a[ia].y<a[ib].y;
    });
    Rep(i,1,k){
        Rep(j,i+1,k){
            mind=min(mind,Length(a[b[i]]-a[b[j]]));
        }
    }
    return mind;
}

int main()
{
    scanf("%d",&n);
    Rep(i,1,n){
        scanf("%lf%lf",&a[i].x,&a[i].y);
    }
    sort(a+1,a+1+n,[=](Point& a,Point& b)->bool{
        return a.x==b.x?(a.y<b.y):(a.x<b.x);
    });

    double ans=dfs(1,n);
    printf("%.4lf\n",ans);

    return 0;
}