【模板】平面最近点对
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#define debug(...) fprintf(stderr, __VA_ARGS__)
#else
#define endl "\n"
#define debug(...) void(0)
#endif
using LL = long long;
constexpr int N = 1e6 + 10;
struct dot {int x, y;
} a[N];
double dist(dot a, dot b) {return hypot(a.x - b.x, a.y - b.y);
}
int n;
double ans;
multimap<int, int, less<>> mp;
multimap<int, int, less<>>::iterator its[N];
int main() {
#ifndef LOCALcin.tie(nullptr)->sync_with_stdio(false);
#endifcin >> n;for (int i = 1; i <= n; i++) cin >> a[i].x >> a[i].y;sort(a + 1, a + n + 1, [&](dot lhs, dot rhs) { return lhs.x < rhs.x; });ans = dist(a[1], a[2]), ans2 = dist2(a[1], a[2]);for (int i = 1, l = 1; i <= n; i++) {while (l < i && a[i].x - a[l].x >= ans) mp.erase(its[l++]);auto itl = mp.upper_bound(a[i].y - ans);auto itr = mp.lower_bound(a[i].y + ans);auto vec = vector<pair<int, int>>(itl, itr);for (auto [y, x] : vec) ans = min(ans, dist(a[i], {x, y}));its[i] = mp.insert({a[i].y, a[i].x});}cout << fixed << setprecision(4) << ans << endl;return 0;
}
multimap<int, int, less<>> 中的 less<> 是必要的。然后这种做法注意 vec 的大小是严格 \(O(1)\) 的，所以复杂度的 \(O(n\log n)\) 的瓶颈在那个平衡树上。
神经的写法，害得我笑了出来。