22pts TLE 正常分治思路

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 400010;
int n, b[N];
struct node { int x, y; } a[N];
bool cmp(node a, node b) { return a.x == b.x ? a.y < b.y : a.x < b.x; }
bool cmp1(int x, int y) { return a[x].y < a[y].y; }
inline ll dis(int i, int j) { return 1ll * (a[i].x - a[j].x) * (a[i].x - a[j].x) + 1ll * (a[i].y - a[j].y) * (a[i].y - a[j].y); }
ll solve(int l, int r) {
    ll d = 0x7f7f7f7f;
    if (l == r) return d;
    if (l + 1 == r) return dis(l, r);
    int mid = l + r >> 1;
    ll d1 = solve(l, mid), d2 = solve(mid + 1, r);
    d = min(d1, d2);
    int k = 0;
    for (int i = l; i <= r; i++)
        if (abs(a[mid].x - a[i].x) < d) b[++k] = i;
    sort(b + 1, b + k + 1, cmp1);
    for (int i = 1; i < k; i++)
        for (int j = i + 1; j <= k && a[b[j]].y - a[b[i]].y < d; j++) d = min(d, dis(b[i], b[j]));
    return d;
}
int main() {
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i].x >> a[i].y;
    sort(a + 1, a + n + 1, cmp);
    cout << solve(1, n) << '\n';
    return 0;
}