自动搬运

查看原文

来自洛谷，原作者为

	feecle6418 **

搬运于2025-08-24 22:12:03，当前版本为作者最后更新于2019-11-20 19:28:19，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

矩形切割裸题。

什么叫矩形切割？就是维护一个不相交矩形组成的集合，支持插入。不过这道题维护的是立方体，思想是一样的。

结合核心代码讲解如下：

void Add(int x1,int y1,int z1,int x2,int y2,int z2){
	a[++tot]=(Cube){x1,y1,z1,x2,y2,z2};//加入新长方体
}
void Cut(int i,int x1,int y1,int z1,int x2,int y2,int z2,int z){
//z表示维度
	if(!z){
		int k1=max(x1,a[i].x1),k2=min(x2,a[i].x2);
        //得到Cut后长方体顶点的x坐标
		if(a[i].x1<k1)Add(a[i].x1,a[i].y1,a[i].z1,k1,a[i].y2,a[i].z2);
        //将原长方体Cut成这个新长方体两边的两部分，这是左边
		if(k2<a[i].x2)Add(k2,a[i].y1,a[i].z1,a[i].x2,a[i].y2,a[i].z2);
        //右边
		Cut(i,k1,y1,z1,k2,y2,z2,1);
        //另外一个维度上也一样
	}
	else if(z==1){
		int k1=max(y1,a[i].y1),k2=min(y2,a[i].y2);
		if(a[i].y1<k1)Add(x1,a[i].y1,a[i].z1,x2,k1,a[i].z2);//y、z维上同理
		if(k2<a[i].y2)Add(x1,k2,a[i].z1,x2,a[i].y2,a[i].z2);
		Cut(i,x1,k1,z1,x2,k2,z2,2);
	}
	else {
		int k1=max(z1,a[i].z1),k2=min(z2,a[i].z2);
		if(a[i].z1<k1)Add(x1,y1,a[i].z1,x2,y2,k1);
		if(k2<a[i].z2)Add(x1,y1,k2,x2,y2,a[i].z2);
	}
}

主程序中调用如下：

for(int i=1,x,y,z,r;i<=q;i++){
	scanf("%d%d%d%d",&x,&y,&z,&r);
	int x1=x-r,x2=x+r,y1=y-r,y2=y+r,z1=z-r,z2=z+r;//长方体的顶点
	for(int j=1;j<=tot;j++){
		if(a[j].x1>=x2||a[j].y1>=y2||a[j].x2<=x1||a[j].y2<=y1||a[j].z1>=z2||a[j].z2<=z1)continue;//若不相交则跳过，不用切割
		Cut(j,x1,y1,z1,x2,y2,z2,0);//切割原长方体
		a[j]=a[tot],j--,tot--;//删除原长方体（原长方体已经被分成许多与现在的长方体不相交的小长方体）
	}
	Add(x1,y1,z1,x2,y2,z2);
}