题目链接：http://acm.split.hdu.edu.cn/showproblem.php?pid=5992

题意：给出n个酒店，每个酒店有一个花费和坐标。然后给出m个询问，输出离询问最近并且花费在询问要求内的酒店。

解法：第一个想法是两种东西按照花费排序，每次插入新酒店。但是这个插入比较麻烦，在kdtree退化的时候需要及时重构（套个替罪羊树啥的）。 还有一种就是直接建三维kdtree，然后对于每一个询问，如果一个节点范围内最小第三维比询问大，那么可以直接忽略。计算的时候只要算上两维的距离即可。（似乎这样比较慢的）。


#include <bits/stdc++.h>
using namespace std;
const int maxn = 200010;
typedef long long LL;
const LL inf = 1e18;
LL n, m, D, root;
struct node{
    LL l, r, d[3], mx[3], mi[3], c, id;
}a[maxn];
bool cmp(node x, node y){
    return x.d[D] < y.d[D];
}
void up(LL k, LL s){
    for(LL i=0; i<3; i++){
        a[k].mi[i] = min(a[k].mi[i], a[s].mi[i]);
        a[k].mx[i] = max(a[k].mx[i], a[s].mx[i]);
    }
}
LL build(LL l, LL r, LL dd){
    D=dd;LL mid=(l+r)/2;
    nth_element(a+l+1,a+mid+1,a+r+1,cmp);
    for(LL i=0; i<3; i++) a[mid].mi[i]=a[mid].mx[i]=a[mid].d[i];
    if(l!=mid) a[mid].l=build(l,mid-1,(dd+1)%3);else a[mid].l=0;
    if(mid!=r) a[mid].r=build(mid+1,r,(dd+1)%3);else a[mid].r=0;
    if(a[mid].l) up(mid,a[mid].l);
    if(a[mid].r) up(mid,a[mid].r);
    return mid;
}
LL Sqr(LL x){
    return x*x;
}
LL x,y,z,ans,dis;
LL getdis(LL p){
    LL res=0;
    if(z<a[p].mi[2]) return inf;
    if(x>a[p].mx[0]) res+=Sqr(x-a[p].mx[0]);
    if(x<a[p].mi[0]) res+=Sqr(a[p].mi[0]-x);
    if(y>a[p].mx[1]) res+=Sqr(y-a[p].mx[1]);
    if(y<a[p].mi[1]) res+=Sqr(a[p].mi[1]-y);
    return res;
}
void ask(LL p){
    LL dl,dr,d0=0;
    if(a[p].d[2]>z) d0=inf;
    if(d0==0){
        d0+=Sqr(a[p].d[0]-x)+Sqr(a[p].d[1]-y);
        if(d0<dis){
            dis=d0;
            ans=p;
        }else if(d0==dis){
            if(a[p].id<a[ans].id){
                ans=p;
            }
        }
    }
    if(a[p].l) dl=getdis(a[p].l);else dl=inf;
    if(a[p].r) dr=getdis(a[p].r);else dr=inf;
    if(dl<dr){if(dl<=dis)ask(a[p].l);if(dr<=dis)ask(a[p].r);}
    else{if(dr<=dis)ask(a[p].r);if(dl<=dis)ask(a[p].l);}
}
int main(){
    LL T;
    scanf("%lld", &T);
    while(T--){
        scanf("%lld%lld", &n,&m);
        for(LL i=1; i<=n; i++){
            for(LL j=0;j<3;j++) scanf("%lld", &a[i].d[j]);
            a[i].l=a[i].r=0;
            a[i].id=i;
        }
        root=build(1, n, 0);
        for(LL i=1; i<=m; i++){
            scanf("%lld%lld%lld", &x,&y,&z);
            dis=inf;
            ans=-1;
            ask(root);
            printf("%lld %lld %lld\n",a[ans].d[0],a[ans].d[1],a[ans].d[2]);
        }
    }
    return 0;
}