题意：
给出若干个点，在给出一个定点，求距离该定点最近的m个点。
思路：
我们已经知道kd-tree可以得到最近邻，实际上M近邻，只需要维护一个size为M的优先队列就可以了。
需要注意，优先队列的元素一定要先定义小于关系orz
以及这次采用了轮盘转的策略划分维度，也就是按照深度，所有维度轮流作为split-method（实际用起来效果还是挺棒的orz
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 |
/* *********************************************** Author :111qqz Created Time :2017年10月08日 星期日 23时18分42秒 File Name :4347.cpp ************************************************ */ #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> #include <string> #include <cmath> #include <cstdlib> #include <ctime> #define PB push_back #define fst first #define sec second #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define ms(a,x) memset(a,x,sizeof(a)) typedef long long LL; #define pi pair < int ,int > #define MP make_pair using namespace std; const double eps = 1E-8; const int dx4[4]={1,0,0,-1}; const int dy4[4]={0,-1,1,0}; const int inf = 0x3f3f3f3f; const int N=5E4+7; const int M = 10; int n,m,k,t; int idx; struct Point { LL coor[M]; int id; void print() { for ( int i = 1 ; i <= k ; i++) printf("%lld%c",coor[i],i==k?'\n':' '); } bool operator < (const Point &u)const { return coor[idx]<u.coor[idx]; } }po[N]; typedef pair< LL,Point >PI; priority_queue< PI >pq; //用优先队列一定要定义小于关系啊orz...我怎么这么傻 struct KdTree { Point p[N<<2]; bool leaf[N<<2]; void build ( int l,int r, int rt = 1,int dep=0) { if (l>r) return; leaf[rt] = false; leaf[rt<<1] = leaf[rt<<1|1] = true; idx = dep % k; int mid = (l+r)>>1; nth_element(po+l,po+mid,po+r+1); p[rt] = po[mid]; build(l,mid-1, rt<<1,dep+1); build(mid+1,r,rt<<1|1,dep+1); } void query(Point tar,int rt=1,int dep=0) { if (leaf[rt]) return; PI cur(0,p[rt]); for ( int i = 1 ; i <= k ; i++) cur.fst += (p[rt].coor[i]-tar.coor[i])*(p[rt].coor[i]-tar.coor[i]); int idx = dep%k; int x=rt<<1,y=rt<<1|1,flag=0; LL d = tar.coor[idx]-p[rt].coor[idx]; if (d>0) swap(x,y); if (!leaf[x]) query(tar,x,dep+1); if (pq.size()<m) pq.push(cur),flag=1; else { if (cur.fst < pq.top().fst) pq.pop(),pq.push(cur); if (d*d<pq.top().fst) flag = 1; } //cout<<pq.top().second.coor[0]<<" "<<pq.top().second.coor[1]<<endl; if (!leaf[y]&&flag) query(tar,y,dep+1); } }kd; int main() { #ifndef ONLINE_JUDGE freopen("./in.txt","r",stdin); #endif while (~scanf("%d %d",&n,&k)) { for ( int i = 1 ; i <= n ; i++) { for ( int j = 1 ; j <= k ; j++) scanf("%lld",&po[i].coor[j]); } scanf("%d",&t); kd.build(1,n); while (t--) { Point ask; for ( int i = 1 ; i <= k ; i++) scanf("%lld",&ask.coor[i]); scanf("%d",&m); kd.query(ask); printf("the closest %d points are:\n",m); Point ret[20]; //cout<<"pq_siz:"<<pq.size()<<" pq.top()"<<pq.top().sec.coor[1]<<endl; for ( int i = 1 ; !pq.empty() ; i++) ret[i] = pq.top().second,pq.pop(); for ( int i = m ; i >= 1 ; i--) ret[i].print(); } } #ifndef ONLINE_JUDGE fclose(stdin); #endif return 0; } |
说点什么
您将是第一位评论人！