既见君子

BZOJ 3053 the closest M points

唔因为最近在复习计算几何所以就来学kdtree了（这是很有关系的！虽然kdtree属于数据结构），之前在oj7上过了一道平面最近点对，恩后来调这道题郁闷了很久结果是which忘了赋值，哎呀呀我要被自己蠢死了，以此来纪念蠢哭了的我，恩现在就可以开心的去学带插入kdtree啦！

code：

#include<cstdio>
#include<stack>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;
const int maxn=50000+5;
int k,which;
struct Point{
        int p[6],id;
        void read(){
                for(int i=1;i<=k;++i) scanf("%d",&p[i]);
        }
        void print(){
                for(int i=1;i<k;++i) printf("%d ",p[i]);
                printf("%d\n",p[k]);
        }
        bool operator <(const Point &c)const{
                return p[which]<c.p[which];
        }
} T[maxn],op,st[maxn];
int met[maxn];
#define eps 1e-7
int sgn(double v){
        if(fabs(v)<eps) return 0;
        return v>0?1:-1;
}
struct node{
        double dis;
        int id;
        bool operator <(const node &c)const{
                return sgn(dis-c.dis)<0;
        }
};
priority_queue<node> q;
void build(int L,int R,int dep){
        if(L>R) return ;
        int mid=(L+R)>>1;
        met[mid]=dep%k+1;
        which=met[mid];
        nth_element(T+L,T+mid,T+R+1);
        build(L,mid-1,dep+1);
        build(mid+1,R,dep+1);
}
int m,n;
double sqr(double v){
        return v*v;
}
double dis(Point a,Point b){
        double ret=0;
        for(int i=1;i<=k;++i) ret+=sqr(a.p[i]-b.p[i]);
        return sqrt(ret);
}
void query(int L,int R){
        if(L>R) return ;
        int mid=(L+R)>>1;
        double now=dis(op,T[mid]);
        if(q.size()<m) q.push((node){now,T[mid].id});
        else if(now<q.top().dis){
                q.pop();
                q.push((node){now,T[mid].id});
        }
        if(op.p[met[mid]]<T[mid].p[met[mid]]){
                query(L,mid-1);
                if(q.size()<m||q.top().dis+op.p[met[mid]]>T[mid].p[met[mid]]) query(mid+1,R);
        }
        else {
                query(mid+1,R);
                if(q.size()<m||op.p[met[mid]]-q.top().dis<T[mid].p[met[mid]]) query(L,mid-1);
        }
}
stack<node> sta;
int main(){
        freopen("3053.in","r",stdin);
        freopen("3053.out","w",stdout);
        while(scanf("%d%d",&n,&k)!=EOF){
                for(int i=1;i<=n;++i) T[i].read(),T[i].id=i,st[i]=T[i];
                build(1,n,0);
                int t;
                scanf("%d",&t);
                while(t--){
                        op.read();
                        scanf("%d",&m);
                        query(1,n);
                        printf("the closest %d points are:\n",m);
                        while(q.size()){
                                sta.push(q.top());
                                q.pop();
                        }
                        while(sta.size()){
                                st[sta.top().id].print();
                                sta.pop();
                        }
                }
        }
        return 0;
}