2015
05-23

The Closest M Points

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?

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.

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.

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

#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=55555,K=5;
const int inf=0x3f3f3f3f;

#define sqr(x) (x)*(x)
int k,n,idx;   //k涓虹淮鏁�,n涓虹偣鏁�
struct point
{
int x[K];
bool operator < (const point &u) const
{
return x[idx]<u.x[idx];
}
}po[N];

typedef pair<double,point>tp;
priority_queue<tp>nq;

struct kdTree
{
point pt[N<<2];
int son[N<<2];

void build(int l,int r,int rt=1,int dep=0)
{
if(l>r) return;
son[rt]=r-l;
son[rt*2]=son[rt*2+1]=-1;
idx=dep%k;
int mid=(l+r)/2;
nth_element(po+l,po+mid,po+r+1);
pt[rt]=po[mid];
build(l,mid-1,rt*2,dep+1);
build(mid+1,r,rt*2+1,dep+1);
}
void query(point p,int m,int rt=1,int dep=0)
{
if(son[rt]==-1) return;
tp nd(0,pt[rt]);
for(int i=0;i<k;i++) nd.first+=sqr(nd.second.x[i]-p.x[i]);
int dim=dep%k,x=rt*2,y=rt*2+1,fg=0;
if(p.x[dim]>=pt[rt].x[dim]) swap(x,y);
if(~son[x]) query(p,m,x,dep+1);
if(nq.size()<m) nq.push(nd),fg=1;
else
{
if(nd.first<nq.top().first) nq.pop(),nq.push(nd);
if(sqr(p.x[dim]-pt[rt].x[dim])<nq.top().first) fg=1;
}
if(~son[y]&&fg) query(p,m,y,dep+1);
}
}kd;
int main()
{
while(scanf("%d%d",&n,&k)!=EOF)
{
for(int i=0;i<n;i++)
for(int j=0;j<k;j++)
scanf("%d",&po[i].x[j]);
kd.build(0,n-1);
int t,m;
scanf("%d",&t);
while(t--)
{
printf("the closest %d points are:\n", m);
point pt[20];
for(int j=0;!nq.empty();j++)
pt[j]=nq.top().second,nq.pop();
for(int j=m-1;j>=0;j--,putchar(10))
for(int z=0;z<k;z++)
if(z) printf(" %d",pt[j].x[z]);
else printf("%d",pt[j].x[z]);
}
}
return 0;
}

1. 就那一群西方被洗脑的冥煮奴隶向来不怀疑他们自己媒体，说洗脑，我们向来会思考。美国是不允许政府控制媒体，就你这句话，应该是你被他们洗脑了吧，说真的还是多看书吧，少翻墙以免头着地。

2. 就那一群西方被洗脑的冥煮奴隶向来不怀疑他们自己媒体，说洗脑，我们向来会思考。美国是不允许政府控制媒体，就你这句话，应该是你被他们洗脑了吧，说真的还是多看书吧，少翻墙以免头着地。

3. 就那一群西方被洗脑的冥煮奴隶向来不怀疑他们自己媒体，说洗脑，我们向来会思考。美国是不允许政府控制媒体，就你这句话，应该是你被他们洗脑了吧，说真的还是多看书吧，少翻墙以免头着地。

4. 就那一群西方被洗脑的冥煮奴隶向来不怀疑他们自己媒体，说洗脑，我们向来会思考。美国是不允许政府控制媒体，就你这句话，应该是你被他们洗脑了吧，说真的还是多看书吧，少翻墙以免头着地。

5. 就那一群西方被洗脑的冥煮奴隶向来不怀疑他们自己媒体，说洗脑，我们向来会思考。美国是不允许政府控制媒体，就你这句话，应该是你被他们洗脑了吧，说真的还是多看书吧，少翻墙以免头着地。

6. 就那一群西方被洗脑的冥煮奴隶向来不怀疑他们自己媒体，说洗脑，我们向来会思考。美国是不允许政府控制媒体，就你这句话，应该是你被他们洗脑了吧，说真的还是多看书吧，少翻墙以免头着地。

7. 就那一群西方被洗脑的冥煮奴隶向来不怀疑他们自己媒体，说洗脑，我们向来会思考。美国是不允许政府控制媒体，就你这句话，应该是你被他们洗脑了吧，说真的还是多看书吧，少翻墙以免头着地。