The Closest M Points
Time Limit: 16000/8000 MS (Java/Others) Memory Limit: 98304/98304 K (Java/Others)
Total Submission(s): 5599 Accepted Submission(s): 1780
Problem Description
The course of Software Design and Development Practice is objectionable. ZLC is facing a serious problem .There are many points in K-dimensional space .Given a point. ZLC need to find out the closest m points. Euclidean distance is used as the distance metric between two points. The Euclidean distance between points p and q is the length of the line segment connecting them.In Cartesian coordinates, if p = (p1, p2,…, pn) and q = (q1, q2,…, qn) are two points in Euclidean n-space, then the distance from p to q, or from q to p is given by:
Can you help him solve this problem?
Input
In the first line of the text file .there are two non-negative integers n and K. They denote respectively: the number of points, 1 <= n <= 50000, and the number of Dimensions,1 <= K <= 5. In each of the following n lines there is written k integers, representing the coordinates of a point. This followed by a line with one positive integer t, representing the number of queries,1 <= t <=10000.each query contains two lines. The k integers in the first line represent the given point. In the second line, there is one integer m, the number of closest points you should find,1 <= m <=10. The absolute value of all the coordinates will not be more than 10000.
There are multiple test cases. Process to end of file.
Output
For each query, output m+1 lines:
The first line saying :”the closest m points are:” where m is the number of the points.
The following m lines representing m points ,in accordance with the order from near to far
It is guaranteed that the answer can only be formed in one ways. The distances from the given point to all the nearest m+1 points are different. That means input like this:
2 2
1 1
3 3
1
2 2
1
will not exist.
Sample Input
3 2
1 1
1 3
3 4
2
2 3
2
2 3
1
Sample Output
the closest 2 points are:
1 3
3 4
the closest 1 points are:
1 3
题目链接：HDU 4347
最后一道$KD-tree$题目，但是$WA$很久，最后发现是$build$的时候节点的$mn$和$mx$忘记赋值了……，这道是最后一道$KD-tree$了，溜了溜了
代码: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
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
using namespace std;
typedef long long LL;
const int N = 50010;
int n, K, m, idx, rt, sz;
struct KD
{
int d[5], mn[5], mx[5], ls, rs;
LL v;
void init(const KD &p)
{
ls = rs = 0;
for (int i = 0; i < K; ++i)
d[i] = mn[i] = mx[i] = p.d[i];
}
bool operator < (const KD &rhs)const
{
return v < rhs.v;
}
} T[N], arr[N], temp, ans[20];
priority_queue<KD>Q;
void init()
{
sz = rt = 0;
}
inline bool cmp(const KD &x, const KD &y)
{
return x.d[idx] < y.d[idx];
}
inline void pushup(const int &x)
{
if (T[x].ls)
{
for (int i = 0; i < K; ++i)
{
T[x].mn[i] = min(T[x].mn[i], T[T[x].ls].mn[i]);
T[x].mx[i] = max(T[x].mx[i], T[T[x].ls].mx[i]);
}
}
if (T[x].rs)
{
for (int i = 0; i < K; ++i)
{
T[x].mn[i] = min(T[x].mn[i], T[T[x].rs].mn[i]);
T[x].mx[i] = max(T[x].mx[i], T[T[x].rs].mx[i]);
}
}
}
void build(int &k, int l, int r, int dim)
{
idx = dim % K;
int mid = MID(l, r);
nth_element(arr + l, arr + mid, arr + r + 1, cmp);
T[k = ++sz] = arr[mid];
if (l < mid)
build(T[k].ls, l, mid - 1, dim + 1);
if (mid < r)
build(T[k].rs, mid + 1, r, dim + 1);
pushup(k);
}
inline LL sqr(LL x)
{
return x * x;
}
inline LL Dis(int a[], int b[])
{
LL ret = 0;
for (int i = 0; i < K; ++i)
ret += sqr((LL)a[i] - (LL)b[i]);
return ret;
}
inline LL partionMin(const int &k)
{
LL ret = 0;
for (int i = 0; i < K; ++i)
{
if (temp.d[i] < T[k].mn[i])
ret += sqr((LL)T[k].mn[i] - (LL)temp.d[i]);
if (temp.d[i] > T[k].mx[i])
ret += sqr((LL)temp.d[i] - (LL)T[k].mx[i]);
}
return ret;
}
void Find(int k)
{
LL dm = Dis(T[k].d, temp.d);
T[k].v = dm;
if (Q.size() < m)
Q.push(T[k]);
else if (T[k].v < Q.top().v)
{
Q.pop();
Q.push(T[k]);
}
LL dl = T[k].ls ? partionMin(T[k].ls, temp) : INF, dr = T[k].rs ? partionMin(T[k].rs, temp) : INF;
if (dl < dr)
{
if (((int)Q.size() < m || dl < Q.top().v) && dl != INF)
Find(T[k].ls);
if (((int)Q.size() < m || dr < Q.top().v) && dr != INF)
Find(T[k].rs);
}
else
{
if (((int)Q.size() < m || dr < Q.top().v) && dr != INF)
Find(T[k].rs);
if (((int)Q.size() < m || dl < Q.top().v) && dl != INF)
Find(T[k].ls);
}
}
int main(void)
{
int i, j;
while (~scanf("%d%d", &n, &K))
{
init();
for (i = 1; i <= n; ++i)
for (j = 0; j < K; ++j)
scanf("%d", &arr[i].d[j]);
build(rt, 1, n, 0);
int q;
scanf("%d", &q);
while (q--)
{
while (!Q.empty())
Q.pop();
for (i = 0; i < K; ++i)
scanf("%d", &temp.d[i]);
scanf("%d", &m);
Find(rt);
printf("the closest %d points are:\n", m);
for (i = m - 1; i >= 0; --i)
{
ans[i] = Q.top();
Q.pop();
}
for (i = 0; i < m; ++i)
for (j = 0; j < K; ++j)
printf("%d%c", ans[i].d[j], " \n"[j == K - 1]);
}
}
return 0;
}