比赛 |
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;
}