记录编号	161059	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOI 1997]卫星覆盖	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	0.019 s
提交时间	2015-04-30 23:03:38	内存使用	0.29 MiB

#include<cstdio>
using namespace std;
class miku
{
public:
	int lx,ly,lz;
	int rx,ry,rz;
}r[110];
int n,ans=0;
int pan(miku a,miku b)
{
	if(a.lx>=b.rx||a.ly>=b.ry||a.lz>=b.rz||b.lx>=a.rx||b.ly>=a.ry||b.lz>=a.rz) return 1;
	else return 0;
}
miku ne(int lx,int ly,int lz,int rx,int ry,int rz)
{
	miku a;
	a.lx=lx,a.ly=ly,a.lz=lz,a.rx=rx,a.ry=ry,a.rz=rz;
	return a;
}
int cut(miku a,int pos)
{
	int re=0;
	do
	{
		pos++;
	}while(pos<=n&&pan(a,r[pos])==1);
	if(pos>n) re=(a.rx-a.lx)*(a.ry-a.ly)*(a.rz-a.lz);
	else
	{
		if(a.lx<r[pos].lx)
		{
			re+=cut(ne(a.lx,a.ly,a.lz,r[pos].lx,a.ry,a.rz),pos);
			a.lx=r[pos].lx;
		}
		if(a.rx>r[pos].rx)
		{
		re+=cut(ne(r[pos].rx,a.ly,a.lz,a.rx,a.ry,a.rz),pos);
		a.rx=r[pos].rx;
		}
		if(a.ly<r[pos].ly)
		{
			re+=cut(ne(a.lx,a.ly,a.lz,a.rx,r[pos].ly,a.rz),pos);
			a.ly=r[pos].ly;
		}
		if(a.ry>r[pos].ry)
		{
			re+=cut(ne(a.lx,r[pos].ry,a.lz,a.rx,a.ry,a.rz),pos);
			a.ry=r[pos].ry;
		}
		if(a.lz<r[pos].lz)
		{
			re+=cut(ne(a.lx,a.ly,a.lz,a.rx,a.ry,r[pos].lz),pos);
			a.lz=r[pos].lz;
		}
		if(a.rz>r[pos].rz)
		{
			re+=cut(ne(a.lx,a.ly,r[pos].rz,a.rx,a.ry,a.rz),pos);
			a.rz=r[pos].rz;
		}
	}
	return re;
}
int main()
{
	freopen("satellitecover.in","r",stdin);
	freopen("satellitecover.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		int x,y,z,q;
		scanf("%d%d%d%d",&x,&y,&z,&q);
		r[i].lx=x-q;r[i].ly=y-q;r[i].lz=z-q;
		r[i].rx=x+q;r[i].ry=y+q;r[i].rz=z+q;
	}
	for(int i=n;i>=1;i--)
	ans+=cut(r[i],i);
	printf("%d",ans);
	return 0;
}