Description

给出一个长方体的箱子，还有在箱子里面的N个长方体的盒子，箱子和盒子的各个边都是平行于某个三维坐标轴。现在要求你找出其中最大的立方体空间，输出它的长度。

首先这个空间必须位于箱子里面，而且不能与其它的盒子占的空间冲突。这个空间也必须是各边平行于某个坐标轴。如下图所示。

题解

二分枚举到可能的立方体长度然后用dfs判断是否成立在dfs中枚举每个盒子，如果与n个盒子都没有交集，继续往下搜如果有交集，向三个地方变化位置，这样就可以那80

代码

#include
     
      #include
      
       #include
       
        using namespace std;int n,l,w,h;bool flag;struct edge{
    int x1,y1,z1,x2,y2,z2;}k[2000];void search(int x,int y,int z,int dep,int s){    if (flag) return;    int xx=x+s,yy=y+s,zz=z+s;    if (xx>l||yy>w||zz>h) return;    if (dep>n)     {        flag=1;        return;    }    if (xx<=k[dep].x1||yy<=k[dep].y1||zz<=k[dep].z1||x>=k[dep].x2||y>=k[dep].y2||z>=k[dep].z2)    {        search(x,y,z,dep+1,s);        return;    }    search(k[dep].x2,y,z,1,s);    search(x,k[dep].y2,z,1,s);    search(x,y,k[dep].z2,1,s);}bool check(int x){    flag=0;    search(0,0,0,1,x);    if (flag) return 1;else return 0;}int ef(int l,int r){    int x=-1,mid;    while (l<=r)    {        mid=(l+r)>>1;        if (check(mid))        {            x=mid;            l=mid+1;            }        else r=mid-1;    }    return x;}int main(){    int t;    scanf("%d",&t);    for (int z=1;z<=t;z++)    {        scanf("%d%d%d%d",&n,&l,&w,&h);        for (int i=1;i<=n;i++) scanf("%d%d%d%d%d%d",&k[i].x1,&k[i].y1,&k[i].z1,&k[i].x2,&k[i].y2,&k[i].z2);        int ans=ef(0,min(l,min(w,h)));        cout<<"Case "<
        
         <<": "<
         
          <