HDU 4347 The Closest M Points KD-tree

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

Author

HIT

Source

​​2012 Multi-University Training Contest 5​​

Recommend

​​傳送門​​

題目大意：給出n個K維的點，然後t條詢問，每次詢問給出一個K維的點x，

讓你每次求出離x最近的m個點。

kd-tree的模闆題目……

注意一下kd-tree的建構之中，需要找到一個次元來劃分兩部分，

那麼應該選擇哪一個呢？為了兩邊盡量均衡，我們選擇方差最小的次元。

那麼選擇的應該是哪一個點作為中間點呢？

很容易想到，選擇中位數。

求中位數一開始，我一開始用了sort（好蠢……）

這樣的話build就平白無故多log了……

直接用nth_element！

用法：nth_element(a+L,a+mid,a+R+1,cmp)

a數組，對于[L,R]的區間，mid=(L+R)>>1，

那麼按照cmp裡面（和sort寫法一緻）的規則，

比如cmp裡面是a[x]<a[y] return true，也就是從小到大，

那麼将會把比a[mid]小的所有數移到mid的左邊，比a[mid]大的移到右邊。

其實我們是可以手寫nth_element的，也就是快排裡面的part……

平均時間複雜度O(N)。

hdu的評測機很不穩定啊……

一份代碼，送出三次，最大時間起伏到了1000ms！

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int read(){
    int x=0,f=1;char ch=getchar();
    while (ch<'0' || ch>'9'){if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
const int 
    N=50005,
    K=10;
const ll 
    inf=(ll)1000000000;

int n,Dimension,t;
int split[N];
ll ans;
bool used[N];
double var[K];
struct POINT{
    int Dim[K],id;
}point[N],T,ANS;
bool cmp(POINT x,POINT y){
    return x.Dim[split[t]]<y.Dim[split[t]];
}
void build(int L,int R){
    if (L>R) return;
    int mid=(L+R)>>1;
    t=mid;
    double avg,len=(double)(R-L+1);
    
    split[mid]=0,var[0]=-1.0;
    for (int i=1;i<=Dimension;i++){
        avg=var[i]=0.0;
        for (int j=L;j<=R;j++) avg+=point[j].Dim[i];
        avg/=len;
        for (int j=L;j<=R;j++)
            var[i]+=((double)point[j].Dim[i]-avg)*((double)point[j].Dim[i]-avg);
        var[i]/=len;
        if (var[split[mid]]<var[i]) split[mid]=i;
    }
    
    nth_element(point+L,point+mid,point+R+1,cmp);
    
    build(L,mid-1);
    build(mid+1,R);
}
void query(int L,int R){
    if (L>R) return;
    int mid=(L+R)>>1;
    ll tmp=(ll)0;
    for (int i=1;i<=Dimension;i++)
        tmp+=(ll)(point[mid].Dim[i]-T.Dim[i])*(ll)(point[mid].Dim[i]-T.Dim[i]);
    
    if (!used[point[mid].id] && ans>tmp)
        ans=tmp,ANS=point[mid];
    
    ll radius=(ll)(T.Dim[split[mid]]-point[mid].Dim[split[mid]])*
            (ll)(T.Dim[split[mid]]-point[mid].Dim[split[mid]]);
    if (T.Dim[split[mid]]<=point[mid].Dim[split[mid]]){
        query(L,mid-1);
        if (ans>=radius) query(mid+1,R);
    }    else{
        query(mid+1,R);
        if (ans>=radius) query(L,mid-1);
    }
}
void solve(){
    for (int i=1;i<=n;i++){
        point[i].id=i;
        for (int j=1;j<=Dimension;j++)
            point[i].Dim[j]=read();
    }
    build(1,n);
    
    int m=read(),num;
    while (m--){
        for (int i=1;i<=Dimension;i++)
            T.Dim[i]=read();
        num=read();
        printf("the closest %d points are:\n",num);
        memset(used,0,sizeof(used));
        while (num--){
            ans=inf;
            query(1,n);
            for (int i=1;i<Dimension;i++)
                printf("%d ",ANS.Dim[i]);
            printf("%d\n",ANS.Dim[Dimension]);
            used[ANS.id]=1;
        }
    }
}
int main(){
    while (~scanf("%d%d",&n,&Dimension))
        solve();
    return 0;
}