K-D Tree 模板

#include<bits/stdc++.h>
using namespace std;
using ld = long double;
using ll = long long;const int MAXN = 200005;
const ll INF = ll(2e18);template<int dimensions>
struct kd_tree {struct Point {ll _[dimensions];};ll dist2(const Point &x, const Point &y) const {ll ret = 0;for(int i = 0; i < dimensions; ++i) {ret += 1ll * (x._[i] - y._[i]) * (x._[i] - y._[i]);}return ret;}ld dist(const Point &x, const Point &y) const {return sqrtl(dist2(x, y));}struct Node {int ls, rs;Point x, l, r;}tr[MAXN];int ROOT;ll ans = INF;ll mind2(const Point &x, int y) {if(!y) {return INF;}ll ret = 0;for(int i = 0; i < dimensions; ++i) {ret += 1ll * max({0ll, tr[y].l._[i] - x._[i], x._[i] - tr[y].r._[i]}) * max({0ll, tr[y].l._[i] - x._[i], x._[i] - tr[y].r._[i]});}return ret;}ld mind(const Point &x, int y) {return (!y ? INF : sqrtl(mind2(x, y)));}void pushup(int u) {tr[u].l = tr[u].r = tr[u].x;for(int i = 0; i < dimensions; ++i) {if(tr[u].ls) {tr[u].l._[i] = min(tr[u].l._[i], tr[tr[u].ls].l._[i]), tr[u].r._[i] = max(tr[u].r._[i], tr[tr[u].ls].r._[i]);}if(tr[u].rs) {tr[u].l._[i] = min(tr[u].l._[i], tr[tr[u].rs].l._[i]), tr[u].r._[i] = max(tr[u].r._[i], tr[tr[u].rs].r._[i]);}}}int build(int l, int r, int k) {if(l > r) {return 0;}int mid = (l + r) >> 1;nth_element(tr + l, tr + mid, tr + r + 1, [k](const Node &x, const Node &y) {return x.x._[k] < y.x._[k];});tr[mid].ls = build(l, mid - 1, (k + 1) % dimensions);tr[mid].rs = build(mid + 1, r, (k + 1) % dimensions);pushup(mid);return mid;}void query(int u, int p) {if(!u) {return;}if(p != u) {ans = min(ans, dist2(tr[u].x, tr[p].x));}ll dl = mind2(tr[p].x, tr[u].ls), dr = mind2(tr[p].x, tr[u].rs);if(dl < dr) {if(dl < ans) {query(tr[u].ls, p);}if(dr < ans) {query(tr[u].rs, p);}}else {if(dr < ans) {query(tr[u].rs, p);}if(dl < ans) {query(tr[u].ls, p);}}}
};int n;
kd_tree<2> kdt;int main() {ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);cin >> n;for(int i = 1; i <= n; ++i) {cin >> kdt.tr[i].x._[0] >> kdt.tr[i].x._[1];}kdt.ROOT = kdt.build(1, n, 0);for(int i = 1; i <= n; ++i) {kdt.query(kdt.ROOT, i);}cout << fixed << setprecision(4) << sqrtl(kdt.ans);return 0;
}