二维最近点对

解法1：暴力枚举，复杂度 $O(n^2)$

解法2：分治

$f(l,r)$ 表示求第 $l\sim r$ 点的最近点对

$int\ mid=l+r>>1;$

$f(l,r) = min(f(l,mid), f(mid+1, r), tt);$

$tt$ 表示跨越中间 $mid$ 的最短点对距离，暴力求解即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10, INF = 0x3f3f3f3f;

namespace TLE {  // n^2
int n, m, x[N], y[N];
ll dis(int i, int j) {
    ll dx = x[i] - x[j], dy = y[i] - y[j];
    return dx * dx + dy * dy;
}
int solve() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d%d", &x[i], &y[i]);
    ll ans = 9e18;
    for (int i = 1; i <= n; i++)
        for (int j = i + 1; j <= n; j++)
            ans = min(ans, dis(i, j));
    printf("%lld\n", ans);
    return 0;
}
};  // namespace TLE

namespace AC {  // nlogn
int n, m;
struct T {
    int x, y;
} a[N], b[N];
ll dis(T& l, T& r) {
    ll dx = l.x - r.x, dy = l.y - r.y;
    return dx * dx + dy * dy;
}
ll f(int l, int r) {
    if (l == r) return 9e18;
    if (l + 1 == r) return dis(a[l], a[r]);
    int mid = l + r >> 1, p = 0;
    ll d = min(f(l, mid), f(mid + 1, r)), tt = 9e18;
    double td = sqrt(d);  // 加速关键
    for (int i = l; i <= r; i++)
        if (fabs(a[i].x - a[mid].x) < td) b[++p] = a[i];
    for (int i = 1; i < p; i++)
        for (int j = i + 1; j <= p; j++)
            d = min(d, dis(b[i], b[j]));
    // 可以进行一点优化
    // sort(b + 1, b + 1 + p, [&](T& l, T& r) { return l.y > r.y; });
    // for (int i = 1; i < p; i++)
    //     for (int j = i + 1; j <= p && b[i].y - b[j].y < td; j++)
    //         d = min(d, dis(b[i], b[j]));
    return d;
}
int solve() {
    scanf("%d", &n);
    for (int i = 1, x, y; i <= n; i++)
        scanf("%d%d", &x, &y), a[i] = {x, y};
    sort(a + 1, a + 1 + n, [&](T& l, T& r) { return l.x < r.x; });
    printf("%lld\n", f(1, n));
    //    printf("%.4lf\n",sqrt(1.0*f(1,n)));
    return 0;
}
};  // namespace AC

int main() {
    // TLE::solve();
    AC::solve();
    return 0;
}