平面最近点对

实现

#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
#define inf 0x3f3f3f3f
using namespace std;

const int N = 200010;
const double eps = 1e-6;
struct node {
    double x, y;
};
int n;
node a[N];

double dis (const node& a, const node& b) {
    double dx = a.x - b.x, dy = a.y - b.y;
    return sqrt(dx * dx + dy * dy);
}
bool cmp1 (const node& a, const node& b) {
    if (fabs(a.x - b.x) < eps)
        return a.y < b.y;
    return a.x < b.x;
}
bool cmp2 (const node& a, const node& b) {
    return a.y < b.y;
}
double solve (int l, int r) {
    if (l == r) return inf;
    if (r == l + 1) return dis(a[l], a[r]);

    int mid = l + r >> 1;
    double d1 = solve(l, mid),
        d2 = solve(mid + 1, r),
        d = min(d1, d2);

    vector<node> b; // a[mid].x-d ~ a[mid.x]+d
    for (int i = l; i <= r; ++ i)
        if (fabs(a[i].x - a[mid].x) <= d)
            b.push_back(a[i]);
    
    sort(b.begin(), b.end(), cmp2);
    for (int i = 0; i < b.size(); ++ i)
        for (int j = i + 1; j < b.size(); ++ j)
            if (b[j].y - b[i].y < d)
                d = min(d, dis(b[i], b[j]));
    return d;
}

int main () {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++ i)
        scanf("%lf%lf", &a[i].x, &a[i].y);
    
    sort(a + 1, a + n + 1, cmp1);
    printf("%.4lf", solve(1, n));
    return 0;
}
# 平面最近点对

# 实现

平面最近点对

实现
