自动搬运

查看原文

来自洛谷，原作者为

	xzx34 但就是因为你能这样思考，才意味着你拥有着，能让你越来越强大的力量

搬运于2025-08-24 22:14:08，当前版本为作者最后更新于2020-03-04 11:42:37，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

思路类似于 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;
}
/*