HDU 5992 kd-tree

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

还记得青岛的时候和蕾姐讨论了近三个小时也不知道这是什么东西后来发现是kdtree 于是拖到寒假才补这个算法

写完几道模板题发现多维的kdtree查找最近也是很简单的拓展于是很快1A了这道题它真的只是模板但确实是青岛的金牌题

如果如果如果如果那么多如果可惜没如果...

我花了很长时间去学了一个以后可能再也不会考到的算法

就当是对过去的一些..补偿吧..?

和普通的kdtree相比加了一个价钱的限制条件和一个输出最前面的id的限制条件

先建好树然后直接查询不用插入

对每个点判断dis的时候如果价钱高于预期距离就变为INF 低于预期就没有影响

如果dl 或者 dr 和当前最近的dis 相等就继续ask以得到更小的id

#include<stdio.h>

#include<string.h>

#include<algorithm>

#include<map>

#include<math.h>

#include<queue>

#include<string>

using namespace std;

#define L long long

const L maxn = 200050 ;

const L INF = 999999999999999999 ;

/**

做一个三维的kdtree 进行最近距离的查找 同时记录最近的ans和最近的编号 随时进行对比

getdis函数 如果小于等于z 距离加上0 否则加上INF

*/

L n , m , cmp_d , root ;

struct node {

    L l , r ;

    L d[3] , Max[3] , Min[3] ;

    L c ;

    L id ;

}a[maxn];

bool cmp(node a , node b ){

    return a.d[cmp_d] < b.d[cmp_d] ;

}

void up(L p , L k ) {

    for(L i = 0; i < 3 ; i ++ ){

        a[p].Min[i] = min(a[p].Min[i] , a[k].Min[i]) ;

        a[p].Max[i] = max(a[p].Max[i] , a[k].Max[i]) ;

    }

}

L build(L l, L r , L D) {

    cmp_d = D ;

    L mid = (l+r)/2 ;

    nth_element(a+1+l,a+1+mid,a+1+r,cmp) ;

    for(L i = 0 ;i < 3 ; i ++) a[mid].Min[i] = a[mid].Max[i] = a[mid].d[i] ;

    if(l != mid) a[mid].l = build(l,mid-1,(D+1)%3) ; else a[mid].l = 0 ;

    if(r != mid) a[mid].r = build(mid+1,r,(D+1)%3) ; else a[mid].r = 0 ;

    if(a[mid].r)up(mid,a[mid].r);

    if(a[mid].l)up(mid,a[mid].l);

    return mid ;

}

L x,y,z;

L jl , ans ;

L getdis(L p) {

    L res = 0 ;

    if(z < a[p].Min[2]) return INF + 1 ;

    if(x > a[p].Max[0]) res += (x - a[p].Max[0]) * (x - a[p].Max[0]) ;

    if(x < a[p].Min[0]) res += (a[p].Min[0] - x) * (a[p].Min[0] - x) ;

    if(y > a[p].Max[1]) res += (y - a[p].Max[1]) * (y - a[p].Max[1]) ;

    if(y < a[p].Min[1]) res += (a[p].Min[1] - y) * (a[p].Min[1] - y) ;

    return res ;

}

void ask(L p) {

    L d0 = 0 ;

    L dl , dr ;

    if(a[p].d[2] > z)d0 += INF ;

    if(d0 == 0) {

        d0 += ((a[p].d[0]) - x) * ((a[p].d[0]) - x ) + ((a[p].d[1]) - y) * ((a[p].d[1]) - y )  ;

        if(d0 < jl){

            ans = p ;

            jl = d0 ;

        }

        else if(d0 == jl) {

            if(a[p].id < a[ans].id) {

                ans = p;

            }

        }

    }

    if(a[p].l)dl = getdis(a[p].l) ; else dl = INF + 1 ;

    if(a[p].r)dr = getdis(a[p].r) ; else dr = INF + 1 ;

    if(dl < dr ) {

        if(dl <= jl) ask(a[p].l) ;

        if(dr <= jl) ask(a[p].r) ;

    }

    else {

        if(dr <= jl) ask(a[p].r) ;

        if(dl <= jl) ask(a[p].l) ;

    }

}

int main(){

    L t;

    scanf("%lld",&t);

    while(t-- ) {

        scanf("%lld%lld",&n,&m) ;

        for(L i=1;i<=n;i++){

            for(L k=0;k<3;k++)scanf("%lld",&a[i].d[k]) ;

            a[i].l = a[i].r = 0 ;

            a[i].id = i ;

        }

        root = build(1,n,0);

        for(L i=1;i<=m;i++){

            scanf("%lld%lld%lld",&x,&y,&z) ;

            jl = INF ;

            ans = -1 ;

            ask(root);

            printf("%lld %lld %lld\n",a[ans].d[0],a[ans].d[1],a[ans].d[2]) ;

        }

    }

}