这题KD-Tree询问的顺序会影响结果吗？

KD-Tree不是正解,只是准备用这题练习一下KD-Tree,但是发现最后询问的时候,必须是按照建树过程中排好的顺序去询问才能AC,我试过了shuffle询问的次序也不能AC这是为什么呢？

#include<iostream>
#include<cstring>
#include<algorithm>
#include<chrono>
#include<random>
using namespace std;
typedef long long LL;
const int maxn = 4e5 + 5, INF = 0x3f3f3f3f;
struct Node{
    int l, r;
    int x, y;
    int mn[2], mx[2];
}tr[maxn];
int g[maxn], root, idx;
LL ans = 1e18;

char buf[1<<21],*p1=buf,*p2=buf,obuf[1<<21],*O=obuf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)

// interger
inline int read(){
    int s = 0, w = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9') {
        if (ch == '-') w = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
    return s * w;
}

int get_node(int x, int y){
    tr[++idx].x = x;
    tr[idx].y = y;
    tr[idx].mn[0] = tr[idx].mx[0] = x;
    tr[idx].mn[1] = tr[idx].mx[1] = y;
    return idx;
}

void pushup(int u){
    tr[u].mn[0] = tr[u].mx[0] = tr[u].x;
    tr[u].mn[1] = tr[u].mx[1] = tr[u].y;
    if (tr[u].l){
        for(int i = 0; i < 2; i++){
            tr[u].mn[i] = min(tr[u].mn[i], tr[tr[u].l].mn[i]);
            tr[u].mx[i] = max(tr[u].mx[i], tr[tr[u].l].mx[i]);
        }
    }
    if (tr[u].r){
        for(int i = 0; i < 2; i++){
            tr[u].mn[i] = min(tr[u].mn[i], tr[tr[u].r].mn[i]);
            tr[u].mx[i] = max(tr[u].mx[i], tr[tr[u].r].mx[i]);
        }
    }
}

int build(int l, int r){
    if (l > r) return 0;
    int mid = l + r >> 1;
    double av1 = 0, av2 = 0, va1 = 0, va2 = 0;
    for(int i = l; i <= r; i++) av1 += tr[g[i]].x, av2 += tr[g[i]].y;
    av1 /= r - l + 1, av2 /= r - l + 1;
    for(int i = l; i <= r; i++){
        va1 += (tr[g[i]].x - av1) * (tr[g[i]].x - av1);
        va2 += (tr[g[i]].y - av2) * (tr[g[i]].y - av2);
    }
    if (va1 >= va2){
        nth_element(g + l, g + mid, g + r + 1, [&](int x, int y){
            return tr[x].x < tr[y].x;
        });
    }
    else{
        nth_element(g + l, g + mid, g + r + 1, [&](int x, int y){
            return tr[x].y < tr[y].y;
        });
    }
    tr[g[mid]].l = build(l, mid - 1);
    tr[g[mid]].r = build(mid + 1, r);
    pushup(g[mid]);
    return g[mid];
}

LL f(int a, int b){
    if (!b) return ans;
    LL res = 0;
    if (tr[b].mn[0] > tr[a].x) res += 1LL * (tr[b].mn[0] - tr[a].x) * (tr[b].mn[0] - tr[a].x);
    if (tr[b].mx[0] < tr[a].x) res += 1LL * (tr[a].x - tr[b].mx[0]) * (tr[a].x - tr[b].mx[0]);
    if (tr[b].mn[1] > tr[a].y) res += 1LL * (tr[b].mn[1] - tr[a].y) * (tr[b].mn[1] - tr[a].y);
    if (tr[b].mx[1] < tr[a].y) res += 1LL * (tr[a].y - tr[b].mx[1]) * (tr[a].y - tr[b].mx[1]);
    return res;
}

LL dist(int x, int y){
    return 1LL * (tr[x].x - tr[y].x) * (tr[x].x - tr[y].x) + 1LL * (tr[x].y - tr[y].y) * (tr[x].y - tr[y].y);
}

void query(int u, int x){
    if (!u) return;
    if (u != x) ans = min(ans, dist(x, u));
    LL fl = f(x, tr[u].l), fr = f(x, tr[u].r);
    if (fl < fr){
        if (fl < ans) query(tr[u].l, x);
        if (fr < ans) query(tr[u].r, x);
    }
    else{
        if (fr < ans) query(tr[u].r, x);
        if (fl < ans) query(tr[u].l, x);
    }
}

int main(){

    int n = read();
    for(int i = 1; i <= n; i++){
        int x = read(), y = read();
        get_node(x, y);
        g[i] = i;
    }
    root = build(1, n);
    for(int i = 1; i <= n; i++) query(root, g[i]);
    printf("%lld\n", ans);

}