西宁企业网站营销推广,无极网站建设,上海seo培训中心,wordpress头像旋转Finding Hotels
给定二维平面上nnn个点#xff0c;每个点描述为x,y,cx, y, cx,y,c#xff0c;x,yx, yx,y为坐标#xff0c;ccc为该点的价值#xff0c;
有mmm个询问#xff0c;每次询问给x,y,cx, y, cx,y,c#xff0c;要求#xff0c;点的价值小于等于ccc的条件下每个点描述为x,y,cx, y, cx,y,cx,yx, yx,y为坐标ccc为该点的价值
有mmm个询问每次询问给x,y,cx, y, cx,y,c要求点的价值小于等于ccc的条件下与x,yx, yx,y最近的且编号最小的点。
考虑K-D Tree对K-D Tree的每个节点同时维护三个信息L,R,D,U,Min_cL, R, D, U, Min\_cL,R,D,U,Min_c然后减枝搜索即可。
#include bits/stdc.husing namespace std;typedef long long ll;const int N 3e5 10;int ls[N], rs[N], n, m;int L[N], R[N], D[N], U[N], C[N], d[N];struct Res {int x, y, c, id;
}s[N];bool cmp1(Res a, Res b) {return a.x b.x;
}bool cmp2(Res a, Res b) {return a.y b.y;
}void push_up(int rt) {L[rt] R[rt] s[rt].x;D[rt] U[rt] s[rt].y;C[rt] s[rt].c;if (ls[rt]) {L[rt] min(L[rt], L[ls[rt]]), R[rt] max(R[rt], R[ls[rt]]);D[rt] min(D[rt], D[ls[rt]]), U[rt] max(U[rt], U[ls[rt]]);C[rt] min(C[rt], C[ls[rt]]);}if (rs[rt]) {L[rt] min(L[rt], L[rs[rt]]), R[rt] max(R[rt], R[rs[rt]]);D[rt] min(D[rt], D[rs[rt]]), U[rt] max(U[rt], U[rs[rt]]);C[rt] min(C[rt], C[rs[rt]]);}
}int build(int l, int r) {if (l r) {return 0;}int mid l r 1;double avx 0, avy 0, vax 0, vay 0;for (int i l; i r; i) {avx s[i].x, avy s[i].y;}avx / r - l 1, avy / r - l 1;for (int i l; i r; i) {vax (avx - s[i].x) * (avx - s[i].x);vay (avy - s[i].y) * (avy - s[i].y);}if (vax vay) {nth_element(s l, s mid, s r 1, cmp1);d[mid] 1;}else {nth_element(s l, s mid, s r 1, cmp2);d[mid] 2;}ls[mid] build(l, mid - 1), rs[mid] build(mid 1, r);push_up(mid);return mid;
}ll ans_dis;int ans_id, ans;ll calc(int a, int b) {return 1ll * (s[a].x - s[b].x) * (s[a].x - s[b].x) 1ll * (s[a].y - s[b].y) * (s[a].y - s[b].y);
}ll calc_min(int a, int b) {ll ans 0;if (L[a] s[b].x) {ans (L[a] - s[b].x) * (L[a] - s[b].x); }if (R[a] s[b].x) {ans (s[b].x - R[a]) * (s[b].x - R[a]);}if (D[a] s[b].y) {ans (D[a] - s[b].y) * (D[a] - s[b].y);}if (U[a] s[b].y) {ans (s[b].y - U[a]) * (s[b].y - U[a]);}return ans;
}void query(int l, int r, int v) {if (l r) {return ;}int mid l r 1;ll dis calc(mid, v);if (s[mid].c s[v].c (dis ans_dis || (dis ans_dis s[mid].id ans_id))) {ans_dis dis, ans mid, ans_id s[mid].id;}if (l r) {return ;}ll disl calc_min(ls[mid], v), disr calc_min(rs[mid], v);if (disl ans_dis C[ls[mid]] s[v].c disr ans_dis C[rs[mid]] s[v].c) {if (disl disr) {query(l, mid - 1, v);if (disr ans_dis) {query(mid 1, r, v);}}else {query(mid 1, r, v);if (disl ans_dis) {query(l, mid - 1, v);}}}else {if (disl ans_dis C[ls[mid]] s[v].c) {query(l, mid - 1, v);}if (disr ans_dis C[rs[mid]] s[v].c) {query(mid 1, r, v);}}
}int main() {// freopen(in.txt, r, stdin);// freopen(out.txt, w, stdout);int T;scanf(%d, T);while (T--) {scanf(%d %d, n, m);for (int i 1; i n; i) {scanf(%d %d %d, s[i].x, s[i].y, s[i].c);s[i].id i;}build(1, n);int n1 n;for (int i 1; i m; i) {n1;scanf(%d %d %d, s[n1].x, s[n1].y, s[n1].c);ans_dis 0x3f3f3f3f3f3f3f3f, ans_id 0x3f3f3f3f;query(1, n, n1);printf(%d %d %d\n, s[ans].x, s[ans].y, s[ans].c);}}return 0;
}
