KD tree 超时求助

#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;

struct node{
    double x,y;
}a[202020];

inline bool cmp1(const node &aa,const node &bb)
{
    return aa.x < bb.x;
}

inline bool cmp2(const node &aa,const node &bb)
{
    return aa.y < bb.y;
}

#define poww(a) (a) * (a)
int n,now;
double ans;
int tree[1010101]; 

inline double dis(int u,int v)
{
    return poww(a[u].x - a[v].x) + poww(a[u].y - a[v].y);
}

int assess(int l,int r)
{
    double tot1 = 0,tot2 = 0,ave1 = 0,ave2 = 0;
    for(int i = l; i <= r; i++)ave1 += a[i].x,ave2 += a[i].y;
    ave1 /= (r - l + 1),ave2 /= (r - l + 1);
    for(int i = l; i <= r; i++)tot1 += poww(a[i].x - ave1),tot2 += poww(a[i].y - ave2);
    return tot1 >= tot2;
}

void build(int k,int l,int r)
{
    if(l >= r)return;
    int m = l + r >> 1;
    tree[k] = assess(l,r);
    if(tree[k] == 1)nth_element(a + l,a + m,a + r,cmp1);
    else nth_element(a + l,a + m,a + r,cmp2);
    build(k << 1,l,m-1);
    build(k <<1|1,m+1,r);
}

void query(int k,int l,int r)
{
    if(r <= now)return;
    int m = l + r >> 1;
    if(now != m)ans = min(ans,dis(now,m));
    if(l >= r)return;
    if(tree[k] == 1)
    {
        if(a[now].x < a[m].x)
        {
            query(k << 1,l,m-1);
            if(ans > fabs(a[now].x - a[m].x))query(k << 1|1,m+1,r); 
        }
        else
        {
            query(k << 1|1,m+1,r);
            if(ans > fabs(a[now].x - a[m].x))query(k << 1,l,m-1);   
        } 
    }
    else
    {
        if(a[now].y < a[m].y)
        {
            query(k<<1,l,m-1);
            if(ans > fabs(a[now].y - a[m].y))query(k<<1|1,m+1,r);   
        }
        else
        {
            query(k<<1|1,m+1,r);
            if(ans > fabs(a[now].y - a[m].y))query(k << 1,l,m-1);   
        } 
    }
}

int main()
{
    ans = 1e22; 
    scanf("%d",&n);
    for(int i = 1; i <= n; i++)
    {
        scanf("%lf%lf",&a[i].x,&a[i].y);
    }
    build(1,1,n);
    for(now = 1; now <= n; now++)
    {
        query(1,1,n);
    }
    printf("%.4lf",sqrt(ans));
    return 0;
}