HDU5992FindingHotelsKDtree

题目链接&＃xff1a;http://acm.split.hdu.edu.cn/showproblem.php?pid&＃61;5992

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

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

#include
using namespace std;
const int maxn &＃61; 200010;
typedef long long LL;
const LL inf &＃61; 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] }
void up(LL k, LL s){for(LL i&＃61;0; i<3; i&＃43;&＃43;){a[k].mi[i] &＃61; min(a[k].mi[i], a[s].mi[i]);a[k].mx[i] &＃61; max(a[k].mx[i], a[s].mx[i]);}
}
LL build(LL l, LL r, LL dd){D&＃61;dd;LL mid&＃61;(l&＃43;r)/2;nth_element(a&＃43;l&＃43;1,a&＃43;mid&＃43;1,a&＃43;r&＃43;1,cmp);for(LL i&＃61;0; i<3; i&＃43;&＃43;) a[mid].mi[i]&＃61;a[mid].mx[i]&＃61;a[mid].d[i];if(l!&＃61;mid) a[mid].l&＃61;build(l,mid-1,(dd&＃43;1)%3);else a[mid].l&＃61;0;if(mid!&＃61;r) a[mid].r&＃61;build(mid&＃43;1,r,(dd&＃43;1)%3);else a[mid].r&＃61;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&＃61;0;if(za[p].mx[0]) res&＃43;&＃61;Sqr(x-a[p].mx[0]);if(xa[p].mx[1]) res&＃43;&＃61;Sqr(y-a[p].mx[1]);if(y}
void ask(LL p){LL dl,dr,d0&＃61;0;if(a[p].d[2]>z) d0&＃61;inf;if(d0&＃61;&＃61;0){d0&＃43;&＃61;Sqr(a[p].d[0]-x)&＃43;Sqr(a[p].d[1]-y);if(d0}
int main(){LL T;scanf("%lld", &T);while(T--){scanf("%lld%lld", &n,&m);for(LL i&＃61;1; i<&＃61;n; i&＃43;&＃43;){for(LL j&＃61;0;j<3;j&＃43;&＃43;) scanf("%lld", &a[i].d[j]);a[i].l&＃61;a[i].r&＃61;0;a[i].id&＃61;i;}root&＃61;build(1, n, 0);for(LL i&＃61;1; i<&＃61;m; i&＃43;&＃43;){scanf("%lld%lld%lld", &x,&y,&z);dis&＃61;inf;ans&＃61;-1;ask(root);printf("%lld %lld %lld\n",a[ans].d[0],a[ans].d[1],a[ans].d[2]);}}return 0;
}