博客

题目大意我就不讲了= =

题解

由于内部有密闭空间所以直接在长方体内部BFS肯定不行，那么考虑在整个立方体周围套一个空气层（具体实现可以加上第0和第501行之类的）。通过对空气层进行BFS解决问题。

给每一个格子一个颜色，比如col[i][j][k]=1表示为空气，0表示未到过，2表示有长方体。然后沿着0去BFS，如果遇到2的话就一定是一个表面积的部分，加上即可，BFS过程中一个变量记录已经到过的体积，最后总体积减去统计的就是所求部分。

然后是离散化，500^3好像会T所以离散化一下（说着简单但是代码量好像特别大的样子）

QAQ别怪我代码写得丑还用_之类的变量名。

代码

#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define rep(i,x,y) for(int i=x;i<=y;i++)
using namespace std;
const int maxn=50+10;
const int maxm=500+10;
const int dx[]= {-1,1,0,0,0,0};
const int dy[]= {0,0,1,-1,0,0};
const int dz[]= {0,0,0,0,1,-1};
inline int read()
{
    int ret=0;char ch=getchar();
    while(ch<='0'||ch>'9')ch=getchar();
    for(;ch>='0'&&ch<='9';ch=getchar()) ret=ret*10+ch-'0';
    return ret;
}
struct Node {
    int x0,y0,z0,dx,dy,dz;
    Node() {}
    Node(int x0,int y0,int z0,int dx,int dy,int dz):
        x0(x0),y0(y0),z0(z0),dx(dx),dy(dy),dz(dz) {}
    inline void input() {
        x0=read();
        y0=read();
        z0=read();
        dx=read();
        dy=read();
        dz=read();
    }
}a[maxn];
struct Array { //离散后->离散
    int _[maxn*2],siz;
    Array() {
        memset(_,0,sizeof(_));
    }
    inline void Sort(int n) {
        sort(_+1,_+2*n+1);
    }
    inline void Unique(int n) {
        siz=unique(_+1,_+2*n+1)-_-1;
    }
    inline void input(int i,int o0,int d0) {
        _[(i<<1)-1]=o0;
        _[i<<1]=o0+d0;
    }
} x,y,z;
struct NODE {
    int x,y,z;
    NODE() {}
    NODE(int x,int y,int z):x(x),y(y),z(z) {}
};

int n,sizex,sizey,sizez;
int col[maxn*2][maxn*2][maxn*2];//0:empty 1:air 2:block
inline void ID(int *k,int v1,int v2,int &p1,int &p2,int sz) 
{
    p1=lower_bound(k+1,k+sz+1,v1)-k;
    p2=lower_bound(k+1,k+sz+1,v2)-k;
    return ;
}
inline int inside(int xx,int yy,int zz) 
{
    return xx>=0&&xx<=x.siz&&yy>=0&&yy<=y.siz&&zz>=0&&zz<=z.siz;
}
inline void BFS(int x1,int y1,int z1,int &biao,int &ti) 
{
    biao=ti=0;
    queue<NODE>q;
    q.push(NODE(x1,y1,z1));
    col[x1][y1][z1]=1;

    while(!q.empty()) 
    {
        NODE k=q.front();
        q.pop();
        int d=(::x._[k.x+1]-::x._[k.x])*(::y._[k.y+1]-::y._[k.y])*(::z._[k.z+1]-::z._[k.z]);
        ti=ti+d;
//      cnt++;printf("%d %d %d %d\n",k.x,k.y,k.z,d);
        int x=k.x,y=k.y,z=k.z;
        for(int i=0;i<6;i++) 
        {
            int nx=x+dx[i],ny=y+dy[i],nz=z+dz[i];
            if(inside(nx,ny,nz)) 
            {
                if(!col[nx][ny][nz])
                    col[nx][ny][nz]=1,q.push(NODE(nx,ny,nz));
                else if(col[nx][ny][nz]==2) 
                {
                    if(i==0||i==1) biao=biao+(::y._[ny+1]-::y._[ny])*(::z._[nz+1]-::z._[nz]);
                    if(i==2||i==3) biao=biao+(::x._[nx+1]-::x._[nx])*(::z._[nz+1]-::z._[nz]);
                    if(i==4||i==5) biao=biao+(::x._[nx+1]-::x._[nx])*(::y._[ny+1]-::y._[ny]);
                }
            }
        }
    }
    ti=(x._[x.siz]+1)*(y._[y.siz]+1)*(z._[z.siz]+1)-ti;
    return ;
}
inline void solve() 
{
    memset(col,0,sizeof(col));
    cin>>n;
    for(int i=1; i<=n; i++) 
    {
        a[i].input();
        x.input(i,a[i].x0,a[i].dx);
        y.input(i,a[i].y0,a[i].dy);
        z.input(i,a[i].z0,a[i].dz);
    }
    x.Sort(n);
    y.Sort(n);
    z.Sort(n);
    x.Unique(n);
    y.Unique(n);
    z.Unique(n);
    x._[x.siz+1]=x._[x.siz]+1;
    y._[y.siz+1]=y._[y.siz]+1;
    z._[z.siz+1]=z._[z.siz]+1;
    for(int O_O=1; O_O<=n; O_O++) 
    {
        int i1,i2,j1,j2,k1,k2;
        ID(x._,a[O_O].x0,a[O_O].x0+a[O_O].dx,i1,i2,x.siz);
        ID(y._,a[O_O].y0,a[O_O].y0+a[O_O].dy,j1,j2,y.siz);
        ID(z._,a[O_O].z0,a[O_O].z0+a[O_O].dz,k1,k2,z.siz);
        rep(i,i1,i2-1) rep(j,j1,j2-1) rep(k,k1,k2-1)
        col[i][j][k]=2;
    }
    int biao,ti;
    BFS(0,0,0,biao,ti);
    printf("%d %d\n",biao,ti);
}

int main() {
    int T;
    cin>>T;
    while(T--) solve();
    return 0;
}