题解 P5567 【[SDOI2008]立方体覆盖】

· · 题解

矩形切割裸题。

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

结合核心代码讲解如下：

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);
}