#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;
const int MAXN = 1e6 + 10, INF = 1e9 + 10;
inline int read() {
char c = getchar(); int x = 0, f = 1;
while(c < '0' || c > '9') {if(c == '-')f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
int N, K, WD, root;
int out[MAXN];
struct Point {
int x[6];
bool operator < (const Point &rhs) const {
return x[WD] < rhs.x[WD];
}
}P[MAXN], ask;
#define ls(x) T[x].ls
#define rs(x) T[x].rs
struct KDTree {
int mn[6], mx[6], ls, rs;
Point tp;
}T[MAXN];
struct Ans {
int val, ID;
bool operator < (const Ans &rhs) const{
return val < rhs.val;
}
};
priority_queue<Ans>Q;
int sqr(int x) {
return x * x;
}
void update(int k) {
for(int i = 1; i <= K; i++) {
T[k].mn[i] = T[k].mx[i] = T[k].tp.x[i];
if(ls(k)) T[k].mn[i] = min(T[k].mn[i], T[ls(k)].mn[i]), T[k].mx[i] = max(T[k].mx[i], T[ls(k)].mx[i]);
if(rs(k)) T[k].mn[i] = min(T[k].mn[i], T[rs(k)].mn[i]), T[k].mx[i] = max(T[k].mx[i], T[rs(k)].mx[i]);
}
}
int Build(int l, int r, int wd) {
WD = wd;
if(l > r) return 0;
int mid = l + r >> 1;
nth_element(P + l, P + mid, P + r + 1);
T[mid].tp = P[mid];
T[mid].ls = Build(l, mid - 1, (wd + 1) % K);
T[mid].rs = Build(mid + 1, r, (wd + 1) % K);
update(mid);
return mid;
}
int GetMinDis(Point a, KDTree b) {
//if(b) return INF;
int ans = 0;
for(int i = 1; i <= K; i++) {
if(a.x[i] < b.mn[i]) ans += sqr(b.mn[i] - a.x[i]);
if(a.x[i] > b.mx[i]) ans += sqr(a.x[i] - b.mx[i]);
}
return ans;
}
int Dis(Point a, Point b) {
int ans = 0;
for(int i = 1; i <= K; i++)
ans += sqr(abs(a.x[i] - b.x[i]));
return ans;
}
void Query(int k) {
int ans = Dis(ask, T[k].tp);
if(ans < Q.top().val) Q.pop(), Q.push((Ans){ans, k});
int disl = INF, disr = INF;
if(ls(k)) disl = GetMinDis(ask, T[ls(k)]);
if(rs(k)) disr = GetMinDis(ask, T[rs(k)]);
if(disl < disr) {
if(disl < Q.top().val) Query(ls(k));
if(disr < Q.top().val) Query(rs(k));
}
else {
if(disr < Q.top().val) Query(rs(k));
if(disl < Q.top().val) Query(ls(k));
}
}
main() {
while(scanf("%d %d", &N, &K) != EOF) {
for(int i = 1; i <= N; i++)
for(int j = 1; j <= K; j++)
P[i].x[j] = read();
root = Build(1, N, 0);
int T = read();
while(T--) {
for(int i = 1; i <= K; i++) ask.x[i] = read();
int M = read();
printf("the closest %d points are:\n", M);
for(int i = 1; i <= M; i++) Q.push((Ans){INF, 0});
Query(root);
for(int i = 1; i <= M; i++)
out[i] = Q.top().ID, Q.pop();
for(int i = M; i >= 1; i--)
for(int j = 1; j <= K; j++)
printf("%d%c", P[out[i]].x[j], j != K ? ' ' : '\n');
}
}
}
网友评论