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
|
#include <algorithm> #include <cstring> #include <queue> #include <stack> #define int long long using namespace std; int divi,sz[50100<<2],n,k,m,t; struct { int val[5]; bool operator < (const num &b) const{ return val[divi]<b.val[divi]; }; }a[50100],KDT[50100<<2]; stack<num> S; priority_queue<pair<long long,num> > q; int squ(int x){ return x*x; } void build(int l,int r,int o,int dep){ if(r<l) return; divi=dep%k; sz[o]=r-l; sz[o<<1]=sz[o<<1|1]=-1; int mid=(l+r)>>1; nth_element(a+l,a+mid,a+r+1); KDT[o]=a[mid]; build(l,mid-1,o<<1,dep+1); build(mid+1,r,o<<1|1,dep+1); } void query(int o,int dep,num c){ if(sz[o]==-1) return; int f=0,lson=o<<1,rson=o<<1|1; int dim=dep%k; pair<long long,num> tmp; tmp.second=KDT[o]; tmp.first=0; for(int i=0;i<k;i++) tmp.first+=squ(c.val[i]-tmp.second.val[i]); if(c.val[dim]>=tmp.second.val[dim]) swap(lson,rson); if(~sz[lson]) query(lson,dep+1,c); if(q.size()<m) q.push(tmp),f=1; else{ if(tmp.first<q.top().first) q.pop(),q.push(tmp); if(squ(c.val[dim]-tmp.second.val[dim])<q.top().first) f=1; } if(~sz[rson]&&f) query(rson,dep+1,c); } signed main(){ while(scanf("%lld %lld",&n,&k)==2){ for(int i=0;i<n;i++) for(int j=0;j<k;j++) scanf("%lld",&a[i].val[j]); build(0,n-1,1,0); scanf("%lld",&t); for(int i=1;i<=t;i++){ while(!q.empty()) q.pop(); num x; for(int j=0;j<k;j++) scanf("%lld",&x.val[j]); scanf("%lld",&m); query(1,0,x); printf("the closest %lld points are:n",m); while(!q.empty()) S.push(q.top().second),q.pop(); while(!S.empty()){ printf("%lld",S.top().val[0]); for(int q=1;q<k;q++) printf(" %lld",S.top().val[q]); printf("n"); S.pop(); } } } return 0; }
|
近期评论