hdu 4347 【KD-TREE】

KD-TREE

 #include#include#include#includeusing 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]tp;priority_queuenq;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=pt[rt].x[dim]) swap(x,y);if(~son[x]) query(p,m,x,dep+1);if(nq.size()=0;j--) print(pt[j]);}}return 0;}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！