首页 > ACM题库 > HDU-杭电 > HDU 4347-The Closest M Points[解题报告]HOJ
2015
05-23

HDU 4347-The Closest M Points[解题报告]HOJ

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:
The Beautiful Road

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--)
        {
            point ask;
            for(int j=0;j<k;j++) scanf("%d",&ask.x[j]);
            scanf("%d",&m); kd.query(ask,m);
            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;
}