首页 > 代码库 > acdream1197 Points In Cuboid
acdream1197 Points In Cuboid
题目链接:http://acdream.info/problem?pid=1197
题意:给出一些点。每次给出一个长方体,问在长方体中的点的个数。
思路:kd-tree。
const int N=111111;struct node{ int x[3]; int L,R;};node a[N];int root,n,m;void insert(int u,int k,int d){ d%=3; if(a[k].x[d]<a[u].x[d]) { if(a[u].L==-1) a[u].L=k; else insert(a[u].L,k,d+1); } else { if(a[u].R==-1) a[u].R=k; else insert(a[u].R,k,d+1); }}int p[3],q[3],ans;void cal(int u,int d){ if(u==-1) return; int i; for(i=0;i<3;i++) if(a[u].x[i]<p[i]||a[u].x[i]>q[i]) break; if(i==3) ans++; d%=3; if(a[u].x[d]>=p[d]) cal(a[u].L,d+1); if(a[u].x[d]<=q[d]) cal(a[u].R,d+1);}void deal(){ int i; for(i=1;i<=n;i++) { a[i].L=a[i].R=-1; scanf("%d%d%d",&a[i].x[0],&a[i].x[1],&a[i].x[2]); if(i==1) root=i; else insert(root,i,0); } m=getInt(); while(m--) { for(i=0;i<3;i++) scanf("%d",&p[i]); for(i=0;i<3;i++) { scanf("%d",&q[i]); if(p[i]>q[i]) swap(p[i],q[i]); } ans=0; cal(root,0); printf("%d\n",ans); }}int main(){ int num=0; while(scanf("%d",&n)!=-1) { printf("Case #%d:\n",++num); deal(); }}
acdream1197 Points In Cuboid
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。