首页 > 代码库 > 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