比赛 |
EYOI与SBOI开学欢乐赛5th |
评测结果 |
AAAAAAAAAAAAAAAAAAAA |
题目名称 |
卫星覆盖 |
最终得分 |
100 |
用户昵称 |
op_组撒头屯 |
运行时间 |
0.648 s |
代码语言 |
C++ |
内存使用 |
12.47 MiB |
提交时间 |
2022-09-16 20:49:12 |
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
const int N=100+5;
const int M=1200;
int n;
int x1[N],y11[N],x2[N],y2[N];
int mp[2*M][2*M]={0};
struct sdf{
int id,z,sgn;
}q[2*N];
bool cmp(sdf x,sdf y){
return x.z<y.z;
}
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,r;scanf("%d%d%d%d",&x,&y,&z,&r);
x1[i]=x-r;y11[i]=y-r;x2[i]=x+r;y2[i]=y+r;
q[i*2-1]={i,z-r,1};q[i*2]={i,z+r,-1};
}
sort(q+1,q+2*n+1,cmp);
int s=0;long long ans=0;
for (int p=1;p<2*n;p++){
for (int i=x1[q[p].id]+1;i<=x2[q[p].id];i++){
for (int j=y11[q[p].id]+1;j<=y2[q[p].id];j++){
if (q[p].sgn==1&&mp[i+M][j+M]==0)s++;
if (q[p].sgn==-1&&mp[i+M][j+M]==1)s--;
mp[i+M][j+M]+=q[p].sgn;
}
}
ans+=1ll*s*(q[p+1].z-q[p].z);
}
printf("%lld\n",ans);
return 0;
}