1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
|
#include <algorithm>
#include <cstring>
#include <queue>
#include <stack>
#define int long long
using namespace std;
int divi,sz[50100<<2],n,k,m,t;
struct {
int val[5];
bool operator < (const num &b) const{
return val[divi]<b.val[divi];
};
}a[50100],KDT[50100<<2];
stack<num> S;
priority_queue<pair<long long,num> > q;
int squ(int x){
return x*x;
}
void build(int l,int r,int o,int dep){
if(r<l)
return;
divi=dep%k;
sz[o]=r-l;
sz[o<<1]=sz[o<<1|1]=-1;
int mid=(l+r)>>1;
nth_element(a+l,a+mid,a+r+1);
KDT[o]=a[mid];
build(l,mid-1,o<<1,dep+1);
build(mid+1,r,o<<1|1,dep+1);
}
void query(int o,int dep,num c){
if(sz[o]==-1)
return;
int f=0,lson=o<<1,rson=o<<1|1;
int dim=dep%k;
pair<long long,num> tmp;
tmp.second=KDT[o];
tmp.first=0;
for(int i=0;i<k;i++)
tmp.first+=squ(c.val[i]-tmp.second.val[i]);
if(c.val[dim]>=tmp.second.val[dim])
swap(lson,rson);
if(~sz[lson])
query(lson,dep+1,c);
if(q.size()<m)
q.push(tmp),f=1;
else{
if(tmp.first<q.top().first)
q.pop(),q.push(tmp);
if(squ(c.val[dim]-tmp.second.val[dim])<q.top().first)
f=1;
}
if(~sz[rson]&&f)
query(rson,dep+1,c);
}
signed main(){
while(scanf("%lld %lld",&n,&k)==2){
for(int i=0;i<n;i++)
for(int j=0;j<k;j++)
scanf("%lld",&a[i].val[j]);
build(0,n-1,1,0);
scanf("%lld",&t);
for(int i=1;i<=t;i++){
while(!q.empty())
q.pop();
num x;
for(int j=0;j<k;j++)
scanf("%lld",&x.val[j]);
scanf("%lld",&m);
query(1,0,x);
printf("the closest %lld points are:n",m);
while(!q.empty())
S.push(q.top().second),q.pop();
while(!S.empty()){
printf("%lld",S.top().val[0]);
for(int q=1;q<k;q++)
printf(" %lld",S.top().val[q]);
printf("n");
S.pop();
}
}
}
return 0;
}
|
近期评论