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