题目描述

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?

软工学院的课程很讨厌！ZLC同志遇到了一个头疼的问题：在K维空间里面有许多的点，对于某些给定的点，ZLC需要找到和它最近的m个点。

（这里的距离指的是欧几里得距离：

D(p, q) = D(q, p) =  sqrt((q1 - p1) ^ 2 + (q2 - p2) ^ 2 + (q3 - p3) ^ 2 + ... + (qn - pn) ^ 2)

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

输入格式

第一行，两个非负整数：点数n(1 <= n <= 50000)，和维度数k(1 <= k <= 5)。

接下来的n行，每行k个整数，代表一个点的坐标。

接下来一个正整数：给定的询问数量t(1 <= t <= 10000)

下面2*t行：

第一行，k个整数：给定点的坐标

第二行：查询最近的m个点(1 <= m <= 10)

所有坐标的绝对值不超过10000。

有多组数据！

输出格式

对于每个询问，输出m+1行：

第一行："the closest m points are:" m为查询中的m

接下来m行每行代表一个点，按照从近到远排序。

保证方案唯一，下面这种情况不会出现：

2 2

1 1

3 3

1

2 2

1

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

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

题目来源

k-d tree