K-D tree有点像平衡树，但好像又不太像，就是一个来回切的分治建树，然后暴力加A*查询，详情见代码：
代码：
#include<iostream> #include<cstdio> #include<cmath> #include<ctime> #include<queue> #include<algorithm> #include<cstring> using namespace std; #define duke(i,a,n) for(register int i = a;i <= n;i++) #define lv(i,a,n) for(register int i = a;i >= n;i--) #define clean(a) memset(a,0,sizeof(a)) typedef long long ll; typedef double db; const ll INF = 1e18; template <class T> void read(T &x) { char c; bool op = 0; while(c = getchar(), c < '0' || c > '9') if(c == '-') op = 1; x = c - '0'; while(c = getchar(), c >= '0' && c <= '9') x = x * 10 + c - '0'; if(op) x = -x; } template <class T> void write(T x) { if(x < 0) putchar('-'), x = -x; if(x >= 10) write(x / 10); putchar('0' + x % 10); } const int N = 1e5 + 5; int dim = 0,n = 0; struct node { int ch[2],id; ll d[2],minn[2],maxn[2]; bool operator < (const node &oth) const { return d[dim] < oth.d[dim]; } }t[N << 2],a[N],b[N]; int root,tcnt = 0; void push_up(int now) { for(int i = 0;i < 2;i++) { if(t[now].ch[0]) { t[now].minn[i] = min(t[now].minn[i],t[t[now].ch[0]].minn[i]); t[now].maxn[i] = max(t[now].maxn[i],t[t[now].ch[0]].maxn[i]); } if(t[now].ch[1]) { t[now].minn[i] = min(t[now].minn[i],t[t[now].ch[1]].minn[i]); t[now].maxn[i] = max(t[now].maxn[i],t[t[now].ch[1]].maxn[i]); } } } void build(int &now,int d,int l,int r) { if(l > r) return; dim = d; int mid = (l + r) >> 1; nth_element(a + l,a + mid,a + r + 1); t[now = ++ tcnt] = a[mid];t[now].id = a[mid].id; t[now].minn[0] = t[now].maxn[0] = t[now].d[0]; t[now].maxn[1] = t[now].minn[1] = t[now].d[1]; t[now].ch[0] = t[now].ch[1] = 0; build(t[now].ch[0],d ^ 1,l,mid - 1); build(t[now].ch[1],d ^ 1,mid + 1,r); push_up(now); } ll ans = INF; ll dis(int now,ll *d) { ll ret = 0; for(int i = 0;i < 2;i++) { ret += (t[now].d[i] - d[i]) * (t[now].d[i] - d[i]); } return ret; } ll price(int now,ll *d) { ll ret = 0; for(int i = 0;i < 2;i++) { if(t[now].maxn[i] < d[i]) ret += (d[i] - t[now].maxn[i]) * (d[i] - t[now].maxn[i]); else if(t[now].minn[i] > d[i]) ret += (d[i] - t[now].minn[i]) * (d[i] - t[now].minn[i]); } return ret; } void query(int now,int id) { if(!now) return; if(t[now].id ^ id) ans = min(ans,dis(now,b[id].d)); ll disl = price(t[now].ch[0],b[id].d),disr = price(t[now].ch[1],b[id].d); if(disl < ans) query(t[now].ch[0],id); if(disr < ans) query(t[now].ch[1],id); } int T; int main() { read(T); while(T--) { tcnt = 0; read(n); duke(i,1,n) { read(a[i].d[0]);read(a[i].d[1]); a[i].id = i; b[i] = a[i]; } build(root,0,1,n); duke(i,1,n) { ans = INF; query(root,i); printf("%lld ",ans); } } return 0; }