题解 P5762 【[NOI1997]卫星覆盖】

· · 题解

声明：此算法有很大的理论优化空间（其实几乎是暴力），但是由于此题年代久远，幸能通过此题。算法思路朴素简单，易于理解。

思路类似于 P5490 【模板】扫描线，只不过我扫描的不是线而是面。给到一个立方体时，将它分解为上面和下面，维护必要信息（坐标信息和加减信息），存入一个数组。将这个数组按高度为第一关键字排序，然后按扫描线的模式扫一遍数组暴力统计答案，就能通过此题。时间复杂度为N r r。

#include <bits/stdc++.h>
#define re register int 
#define il inline
#define ll long long
#define x1 _
#define y1 __
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
using namespace std;
const int inf=1e9;
char buf[1<<23],*p1=buf,*p2=buf,obuf[1<<23],*O=obuf;
il int read(){
    char c=getchar();int z=0,f=1;
    while(c!='-'&&(c>'9'||c<'0')) c=getchar();
    if(c=='-') f=-1,c=getchar();
    while(c>='0'&&c<='9') z=(z<<1)+(z<<3)+c-'0',c=getchar();
    return z*f;
}
int f[2005][2005]; 
struct LINE{
    int x1,y1,x2,y2,mark,z;
}q[250];//x1,y1,x2,y2 维护面坐标，z维护高度 
bool cmp(LINE x,LINE y){
    return x.z<y.z;
}
int n,S,ans;
int main (){
    n=read();
    for(re i=1;i<=n;i++){
        int x=read()+1000,y=read()+1000,z=read()+1000,r=read();
        q[(i<<1)-1]={x-r+1,y-r+1,x+r,y+r,1,z-r};//插入队列 
        q[i<<1]={x-r+1,y-r+1,x+r,y+r,-1,z+r};
    }
    n<<=1;//便于操作 
    sort(q+1,q+1+n,cmp);
    for(re i=1;i<n;i++){//最后一个面不考虑 
        for(re j=q[i].x1;j<=q[i].x2;j++)
            for(re k=q[i].y1;k<=q[i].y2;k++){//无脑暴力修改 
                f[j][k]+=q[i].mark;
                if(q[i].mark==1&&f[j][k]==1) S++;
                if(q[i].mark==-1&&f[j][k]==0) S--;
            }
        ans+=(q[i+1].z-q[i].z)*S;
    }
    cout<<ans;
    return 0;
}
/*