分治法解决最近点对

模板题。。
将n个点按x坐标进行排序，分为左右两半，分别求出两半内的最近点对的距离，取最小值设为当前答案，设为ans。然后考虑把两个集合并，在分割线处还有可能会有更优的答案。取分割线左右ans距离内的点，按y坐标排序，用每个点与其左右6个点的距离更新答案即可。（没错是复制下来的）

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <set>
#include <vector>
using namespace std;
const int MAXN = 1e5 + 5;
const double EPS = 1e-6;
double PI;
struct Point
{
    Point() {}
    Point(double _x, double _y): x(_x), y(_y) {}
    double getDis(Point rhs)
    {
        double xx = rhs.x - x, yy = rhs.y - y;
        return sqrt(xx * xx + yy * yy);
    }

    void input(){scanf("%lf%lf", &x, &y);}
    double x, y;
};
double operator ^(Point lhs, Point rhs){return lhs.x * rhs.y - lhs.y * rhs.x;}
Point operator +(Point lhs, Point rhs){return Point(lhs.x + rhs.x, lhs.y + rhs.y);}
Point operator -(Point lhs, Point rhs){return Point(lhs.x - rhs.x, lhs.y - rhs.y);}
Point operator /(Point lhs, double rhs){return Point(lhs.x / rhs, lhs.y / rhs);}
Point operator *(Point lhs, double rhs){return Point(lhs.x * rhs, lhs.y * rhs);}

Point point[MAXN];
int n, s[MAXN];

bool cmpx(int i, int j)
{
    return point[i].x < point[j].x - EPS;
}

bool cmpy(int i, int j)
{
    return point[i].y < point[j].y - EPS;
}

double _minDist(int l, int r)
{
    double ans = 1e100;
    if(r - l <= 20)
    {
        for(int i = l; i <= r; ++i)
        {
            for(int j = i + 1; j <= r; ++j)
            {
                ans = min(ans, point[s[i]].getDis(point[s[j]]));
            }
        }
        return ans;
    }
    int tl, tr;
    int m = (l + r) / 2;
    ans = min(_minDist(l, m), _minDist(m + 1, r));
    for(tl = l; point[s[tl]].x < point[s[m]].x - ans; ++tl);
    for(tr = r; point[s[tr]].x > point[s[m]].x + ans; --tr);
    sort(s + tl, s + tr + 1, cmpy);
    for(int i = tl; i <= tr; ++i)
    {
        for(int j = i + 1; j <= min(tr, i + 6); ++j)
        {
            ans = min(ans, point[s[i]].getDis(point[s[j]]));
        }
    }
    sort(s + tl, s + tr + 1, cmpx);
    return ans;
}

double getMinDist()
{
    for(int i = 0; i < n; ++i) s[i] = i;
    sort(s, s + n, cmpx);
    return _minDist(0, n - 1);
}

int main()
{
    while(scanf("%d", &n) && n != 0)
    {
        for(int i = 0; i < n; ++i) point[i].input();
        printf("%.2lf\n", getMinDist() / 2.0);
    }
}