【JZOJ2748】【2012中山市选】最大立方体空间(二分+扫描线+二维线段树)

xiaoxiao2021-02-28  12

Problem

  给出一个长方体的箱子,还有在箱子里面的N个长方体的盒子,箱子和盒子的各个边都是平行于某个三维坐标轴。现在要求你找出其中最大的立方体空间,输出它的长度。   首先这个空间必须位于箱子里面,而且不能与其它的盒子占的空间冲突。这个空间也必须是各边平行于某个坐标轴。如下图所示。   

Input

  测试文件含有多组数据。测试文件的第一行是数据个数T。接下来是T组数据。   每组数据的第一行是4个整数N,L,W,H。分别表示盒子的个数和箱子的长宽高(分别对应X,Y,Z轴)。   然后N行,每行有6个整数xi yi zi Xi Yi Zi描述了第i个盒子,(xi, yi, zi)表示盒子的后左下角(坐标值最小的那个角),Xi Yi Zi则表示前右上角(坐标值最大的那个角)。所有结出的盒子都在箱子里面而且不会相互相交。

Output

  对于每组数据输出一行“Case X: Y”(不带引号,冒号后面有空格),其中X是测试数据编号(从1开始)。Y 是最大立方体空间的边长。如果箱子中没有空余的空间,那么Y就是0。

Hint

T<=2 0<=N<=1000 0<=xi<=Xi<=L<=1000 0<=yi<=Yi<=W<=1000 0<=zi<=Zi<=H<=1000

Solution

容易想到二分答案。那么关键就在于判断二分出的答案是否合法。 设二分出的答案为len,我们先将L、W、H都-len,并将每个盒子的后左下角也都-len。原因下面再描述。 然后,我们需要维护一个二维线段树,维护当前高度的平面中每一块的最小值。 我们可以仿照在平面图形中的扫描线,将箱子和所有盒子的上下表面按高度从小到大排序,高度相等时下表面优先。然后每次扫到下表面时,就在二维线段树中的那块区间+1,扫到上表面就-1。 如果在某一次-1后二维线段树的根节点(即当前高度的平面中的最小值)为0,那么len便合法。因为我们上面都已经将箱子缩小了len,并将盒子的后左下角扩大了len,但是这样依然在某个高度中存在空隙,那就说明如果我们将那个空隙作为我们要找的最大的立方体空间的后左下角,它往前、右、上扩展len格也是可行的,于是len便合法。 在用上/下表面覆盖二维线段树的时候,设这个表面左下角为(x1,y1),右上角为(x2,y2),则将x1变为max(x1+1,0),x2变为min(x2-1,L),y1、y2同理。拿x1来说,如果它本身就<0,x1+1也肯定<=0,那最后结果依然是0;而如果它未+1时卡着边界,那么覆盖之后便不会留有空隙,但是一个合法的len有可能刚好卡住这个表面,所以我们要给它造个空隙。 而上面说到箱子的上下表面也要参与扫描线,是因为我们把它的下表面的高度设为了-1,上表面的高度设为了0,这样,在碰到纵然所有盒子的后左下角都扩大了len都浮空的情况时,扫完箱子的上表面就可以判定此len合法了。而设若不这么做,程序就会从最低的那个浮空盒子开始做起,从而无视了它们下面的那些空隙,于是可能会误判此len非法。 而对于二维线段树,我们在表示一块区间时,若其长度大于宽度,则其两儿子为其长度折半;否则为其宽度折半。这样做的话不仅能正确表示每一种区间从而不会重复下标,也能节省时间。据说还有一种四分法,将其长度、宽度同时折半,但是难打很多。 时间复杂度: O(N(log2N)3) O ( N ( l o g 2 N ) 3 )

Code

#include <cstdio> #include <algorithm> #include <cstring> using namespace std; #define N 1002 #define fo(i,a,b) for(i=a;i<=b;i++) int t,tt,i,n,L,W,H,x[N],y[N],z[N],X[N],Y[N],Z[N],l,r,mid,x1,y1,x2,y2,d,f[N*N*4],tag[N*N*4]; struct box { int x,y,z,X,Y,Z; }b[N]; struct E { int high,num; }o[N*2]; bool operator<(const E &a,const E &b) { return a.high<b.high||a.high==b.high&&a.num<b.num; } void modify(int v,int x,int X,int y,int Y) { if(x1<=x&&x2>=X&&y1<=y&&y2>=Y) { f[v]+=d; tag[v]+=d; return; } if(tag[v]) { f[v*2]+=tag[v], tag[v*2]+=tag[v]; f[v*2+1]+=tag[v],tag[v*2+1]+=tag[v]; tag[v]=0; } if(X-x>Y-y) { int mid=(x+X)>>1; if(x1<=mid)modify(v*2,x,mid,y,Y); if(x2>mid) modify(v*2+1,mid+1,X,y,Y); }else { int mid=(y+Y)>>1; if (y1<=mid)modify(v*2,x,X,y,mid); if (y2>mid) modify(v*2+1,x,X,mid+1,Y); } f[v]=min(f[v*2],f[v*2+1]); } bool check(int r,int L,int W,int H) { int i,m=0; fo(i,1,n) { b[i].x=x[i]-r;b[i].y=y[i]-r;b[i].z=z[i]-r; b[i].X=X[i]; b[i].Y=Y[i]; b[i].Z=Z[i]; o[++m].high=b[i].z;o[m].num=i; o[++m].high=b[i].Z;o[m].num=-i; } sort(o+1,o+m+1); memset(f,0,sizeof f); memset(tag,0,sizeof tag); fo(i,1,m) { if(o[i].high>H)break; box &q=b[abs(o[i].num)]; x1=max(q.x+1,0);y1=max(q.y+1,0); x2=min(q.X-1,L);y2=min(q.Y-1,W); d=o[i].num>0?1:-1; modify(1,0,L,0,W); if(!f[1])return 1; } return 0; } int main() { scanf("%d",&t); fo(tt,1,t) { scanf("%d%d%d%d",&n,&L,&W,&H); fo(i,1,n)scanf("%d%d%d%d%d%d",&x[i],&y[i],&z[i],&X[i],&Y[i],&Z[i]); x[++n]=y[n]=z[n]=-1;X[n]=L;Y[n]=W;Z[n]=0; l=0; r=min(min(L,W),H); while(l<r) { mid=(l+r+1)/2; if(check(mid,L-mid,W-mid,H-mid)) l=mid; else r=mid-1; } printf("Case %d: %d\n",tt,l); } }
转载请注明原文地址: https://www.6miu.com/read-2150277.html

最新回复(0)