「BZOJ3053」The Closest M Points

Description

软工学院的课程很讨厌!ZLC同志遇到了一个头疼的问题:在KK维空间里面有许多的点,对于某些给定的点,ZLC需要找到和它最近的mm个点。
(这里的距离指的是欧几里得距离:D(p,q)=D(q,p)=(q1p1)2+(q2p2)2+(q3p3)2+...+(qnpn)2)D(p, q) = D(q, p) = \sqrt{(q1 - p1) ^ 2 + (q2 - p2) ^ 2 + (q3 - p3) ^ 2 + ... + (qn - pn) ^ 2)}
ZLC要去打Dota,所以就麻烦你帮忙解决一下了……

Input

第一行,两个非负整数:点数n(1n50000)n(1 \leq n \leq 50000),和维度数k(1k5)k(1 \leq k \leq 5)
接下来的nn行,每行kk个整数,代表一个点的坐标。
接下来一个正整数:给定的询问数量t(1t10000)t(1 \leq t \leq 10000)
下面2×t2\times t行:
  第一行,kk个整数:给定点的坐标
  第二行:查询最近的mm个点(1m10)(1 \leq m \leq 10)

所有坐标的绝对值不超过1000010000
多组数据

Output

对于每个询问,输出m+1行:
第一行:“the closest m points are:” mm为查询中的mm
接下来mm行每行代表一个点,按照从近到远排序。
保证方案唯一,下面这种情况不会出现:

1
2
3
4
5
6
2 2
1 1
3 3
1
2 2
1

Sample Input

3 2
1 1
1 3
3 4
2
2 3
2
2 3
1

Sample Output

1
2
3
4
5
the closest 2 points are:
1 3
3 4
the closest 1 points are:
1 3

Solution

Kdtree,getdis等函数千万不要写错,写错的话可能就更暴力一样询问了。

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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<queue>
#include<bitset>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
const int N = 61000;
int n, k;
const int inf = 1e9 + 7;
struct P {
ll x[6];
}a[N], b[N];
int rt, tot;
struct Tree {
P p;
ll x[5], y[5];
int l, r;
}t[N];
int col;
bool cmp(P _x, P _y) {
return _x.x[col] < _y.x[col];
}
void up(int o) {
for(int i = 0; i < k; ++i) {
t[o].x[i] = min(t[o].p.x[i], min(t[t[o].l].x[i], t[t[o].r].x[i]));
t[o].y[i] = max(t[o].p.x[i], max(t[t[o].l].y[i], t[t[o].r].y[i]));
}
}
void build(int &o, int l, int r, int c) {
o = ++tot;
int mid = (l + r) >> 1;
col = c;
nth_element(a + l, a + mid, a + r + 1, cmp);
t[o].p = a[mid];
for(int i = 0; i < k; ++i) t[o].x[i] = t[o].y[i] = a[mid].x[i];
t[o].l = t[o].r = 0;
if(l < mid) build(t[o].l, l, mid - 1, (c + 1) % k);
if(r > mid) build(t[o].r, mid + 1, r, (c + 1) % k);
up(o);
}
int m;
struct Ant {
ll d;
P p;
bool operator < (const Ant _x) const {
return d < _x.d;
}
}st[N];
int top;
priority_queue<Ant>q;
ll dst(P x, P y) {
ll res = 0;
for(int i = 0; i < k; ++i)
res += sqr(x.x[i] - y.x[i]);
return res;
}
ll getdi(P &x, int y) {
ll res = 0;
for(int i = 0; i < k; ++i) {
ll g = max(0ll, t[y].x[i] - x.x[i]) + max(0ll, x.x[i] - t[y].y[i]);
res += sqr(g);
}
return res;
}
void query(int o, P &x) {
Ant tmp ;
tmp.d = dst(t[o].p, x);
tmp.p = t[o].p;
if(q.size() < m) q.push(tmp);
else if(tmp.d < q.top().d) q.pop(),q.push(tmp);
ll lt = 1e18 + 66, rt = 1e18 + 66;
if(t[o].l) lt = getdi(x, t[o].l);
if(t[o].r) rt = getdi(x, t[o].r);
if(lt < rt) {
if(lt < q.top().d || q.size() < m) query(t[o].l, x);
if(rt < q.top().d || q.size() < m) query(t[o].r, x);
} else {
if(rt < q.top().d || q.size() < m) query(t[o].r, x);
if(lt < q.top().d || q.size() < m) query(t[o].l, x);
}
}
int main() {
while(~scanf("%d%d",&n,&k)) {
tot = 0;
for(int i = 0; i < k; ++i)
t[0].x[i] = inf, t[0].y[i] = -inf;
for(int i = 1; i <= n; ++i) {
for(int j = 0; j < k; ++j)
a[i].x[j] = read();
b[i] = a[i];
}
build(rt, 1, n, 0);
int Q = read();
for(int T = 1; T <= Q; ++T) {
P x;
for(int i = 0; i < k; ++i) x.x[i] = read();
m = read();
query(rt, x);
printf("the closest %d points are:\n", m);
top = 0;
while(q.size()) st[++top] = q.top(), q.pop();
while(top) {
for(int j = 0; j < k; ++j) {
if(j > 0) putchar(' ');
printf("%lld", st[top].p.x[j]);
}
puts("");
--top;
}
}
}

return 0;
}