# BZOJ 3053: The Closest M Points(K-D Tree)

Time Limit: 10 Sec  Memory Limit: 128 MB

Submit: 1235  Solved: 418

[Submit][Status][Discuss]

## 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: D(p,q)=D(q,p)=sqrt((q1-p1)^2+(q2-p2)^2+(q3-p3)^2…+(qn-pn)^2 Can you help him solve this problem?

（这里的距离指的是欧几里得距离：D(p, q) = D(q, p) =  sqrt((q1 - p1) ^ 2 + (q2 - p2) ^ 2 + (q3 - p3) ^ 2 + ... + (qn - pn) ^ 2)

ZLC要去打Dota，所以就麻烦你帮忙解决一下了……

【Input】

【Output】

## 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

## Source

k-d tree

```#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;
const int MAXN = 1e6 + 10, INF = 1e9 + 10;
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];
}
#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) {
if(ans < Q.top().val) Q.pop(), Q.push((Ans){ans, k});
int disl = INF, disr = INF;
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++)
root = Build(1, N, 0);
while(T--) {
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');
}
}
} ```

0 条评论

• ### 洛谷P2863 [USACO06JAN]牛的舞会The Cow Prom

ng the other ends of her ropes (if she has any), along with the cows holding the...

• ### POJ3683 Priest John's Busiest Day(2-SAT)

Description John is the only priest in his town. September 1st is the John's bu...

• ### POJ 3292 Semi-prime H-numbers

Description This problem is based on an exercise of David Hilbert, who pedagogi...

• ### HDU 5652 India and China Origins（并查集）

India and China Origins Time Limit: 2000/2000 MS (Java/Others)    Memory Limit:...

• ### POJ 3662 Telephone Lines【Dijkstra最短路+二分求解】

Telephone Lines Time Limit: 1000MS Memory Limit: 65536K Total Submission...

• ### ZOJ 3204 Connect them

Connect them ---- Time Limit: 1 Second      Memory Limit: 32768 KB ---- You have...

• ### POJ--1690 (Your)((Term)((Project)))（字符串处理）

(Your)((Term)((Project))) Time Limit: 1000MS Memory Limit: 10000K Total...

• ### HDU 3367 Pseudoforest(Kruskal)

Pseudoforest Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65536/655...

• ### 仿qq最新侧滑菜单

为了后续对这个项目进行优化，比如透明度动画、背景图的位移动画，以及性能上的优化。 我把这个项目上传到github上面，请大家随时关注。 github地址 htt...

• ### 搜索专题2 | 3D地宫寻路 POJ - 2251

上一篇我们做了一道棋子摆放的题目，采用的是DFS算法，本篇是一篇BFS算法，在刚开始学习搜索算法的时候，会觉得DFS和BFS算法非常相似，因为都是搜索然后得到结...