比赛 EYOI与SBOI开学欢乐赛5th 评测结果 AAAAAAAAAAAAAAAAAAAA
题目名称 卫星覆盖 最终得分 100
用户昵称 ムラサメ 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2022-09-16 21:02:31
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
int n,v,tot=0;
struct node{
	int x1,x2,y1,y2,z1,z2;
}c[5010],a[5010];
bool xj(int i,int j){
	return !(((a[i].x1>=c[j].x2)||(c[j].x1>=a[i].x2))||((a[i].y1>=c[j].y2)||(c[j].y1>=a[i].y2))||((a[i].z1>=c[j].z2)||(c[j].z1>=a[i].z2)));
}
void add(int x1,int x2,int y1,int y2,int z1,int z2){
	a[++tot]=(node){x1,x2,y1,y2,z1,z2};
}
void work(int i,int x1,int x2,int y1,int y2,int z1,int z2,int type){
	if(type==1){
		int k1=max(c[i].x1,x1),k2=min(c[i].x2,x2);
		if(k1>x1){
			add(x1,k1,y1,y2,z1,z2);
		}
		if(k2<x2){
			add(k2,x2,y1,y2,z1,z2);
		}
		work(i,k1,k2,y1,y2,z1,z2,2);
	}
	if(type==2){
		int k1=max(c[i].y1,y1),k2=min(c[i].y2,y2);
		if(k1>y1){
			add(x1,x2,y1,k1,z1,z2);
		}
		if(k2<y2){
			add(x1,x2,k2,y2,z1,z2);
		}
		work(i,x1,x2,k1,k2,z1,z2,3);
	}
	if(type==3){
		int k1=max(c[i].z1,z1),k2=min(c[i].z2,z2);
		if(k1>z1){
			add(x1,x2,y1,y2,z1,k1);
		}
		if(k2<z2){
			add(x1,x2,y1,y2,k2,z2);
		}
	}
}
int main(){
	freopen("satellitecover.in","r",stdin);
	freopen("satellitecover.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i=1,x,y,z,r;i<=n;++i){
		cin>>x>>y>>z>>r;
		c[i].x1=x-r;
		c[i].x2=x+r;
		c[i].y1=y-r;
		c[i].y2=y+r;
		c[i].z1=z-r;
		c[i].z2=z+r;
	}
	for(int i=1;i<=n;++i){
		for(int j=1;j<=tot;++j){
			if(xj(j,i)){
				work(i,a[j].x1,a[j].x2,a[j].y1,a[j].y2,a[j].z1,a[j].z2,1);
				a[j]=a[tot];
				--tot;
				--j;
			}
		}
		add(c[i].x1,c[i].x2,c[i].y1,c[i].y2,c[i].z1,c[i].z2);
	}
	for(int i=1;i<=tot;++i){
		v+=(a[i].x2-a[i].x1)*(a[i].y2-a[i].y1)*(a[i].z2-a[i].z1);
	}
	cout<<v<<endl;
	return 0;
}