uva 12171 Sculpture
原题：
Imagine a box, made of copper plate. Imagine a second one, intersecting the rst one, and several others, intersecting each other (or not). That is how the sculptor Oto Boxing constructs his sculptures. In fact he does not construct that much, he only makes the design; the actual construction is contracted out to a construction company. For the calculation of the costs of construction the company needs to know the total area of copper plate involved. Parts of a box that are hidden in another box are not realized in copper, of course. (Copper is quite expensive, and prices are rising.) After construction, the total construction is plunged into a bath of chemicals. To prevent this bath from running over, the construction company wants to know the total volume of the construction. Given that a construction is a collection of boxes, you are asked to calculate the area and the volume of the construction.
Some of Oto’s designs are connected, others are not. Either way, we want to know the total area and the total volume. It might happen
that the boxes completely enclose space that is not included in any of the boxes (see the second example below). Because the liquid cannot enter that space, its volume must be added to the total volume. Copper plate bordering this space is superfluous, of course, so it does not add to the area.
Input
On the rst line one positive number: the number of testcases, at most 100. After that per testcase:
• One line with an integer n (1 ≤ n ≤ 50): the number of boxes involved.
• n lines with six positive integers x 0 ,y 0 ,z 0 , x ,y,z (1 ≤ x0,y0,z0,x,y,z ≤ 500): the triple (x 0 ,y 0 ,z 0 ) is the vertex of the box with the minimum values for the coordinates and the numbers x, y, z are the dimensions of the box (x, y and z dimension, respectively). All dimensions are in centimeters. The sides of the boxes are always parallel to the coordinate axes.
Output
Per testcase:
• One line with two numbers separated by single spaces: the total amount of copper plate needed
(in cm 2 ), and the total volume (in cm 3 ).
Sample Input
2
2
1 2 3 3 4 5
6 2 3 3 4 5
7
1 1 1 5 5 1
1 1 10 5 5 1
1 1 2 1 4 8
2 1 2 4 1 8
5 2 2 1 4 8
1 5 2 4 1 8
3 3 4 1 1 1
Sample Output
188 120
250 250
中文：（来自紫书）
某雕塑由n（n≤50）个边平行于坐标轴的长方体组成。每个长方体用6个整数x 0 ，y 0 ，z 0 ，x，y，z表示（均为1～500的整数），其中x 0 为长方体的顶点中x坐标的最小值，x表示长方体在x方向的总长度。其他4个值类似定义。你的任务是统计这个雕像的体积和表面积。注意，雕塑内部可能会有密闭的空间，其体积应计算在总体积中，但从“外部”看不见的面不应计入表面积。雕塑可能会由多个连通块组成。
代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn=201;
int n,t;
int nx,ny,nz;
int X1[maxn],Y1[maxn],Z1[maxn],X2[maxn],Y2[maxn],Z2[maxn];
int nX[maxn],nY[maxn],nZ[maxn];
int xMark[1002],yMark[1002],zMark[1002];
int color[101][101][101];
int dx[]={1,-1,0,0,0,0};
int dy[]={0,0,1,-1,0,0};
int dz[]={0,0,0,0,1,-1};
struct Cell
{
int x,y,z;
Cell(int x=0,int y=0,int z=0):x(x),y(y),z(z){}
bool valid() const
{
return x>=0&&x<nx-1 && y>=0&&y<ny-1 && z>=0&&z<nz-1;
}
bool solid() const
{
return color[x][y][z]==1;
}
bool get_vis() const
{
return color[x][y][z]==2;
}
void set_vis() const
{
color[x][y][z]=2;
}
Cell neighbor(int dir) const
{
return Cell(x+dx[dir],y+dy[dir],z+dz[dir]);
}
int volume() const
{
return (nX[x+1]-nX[x])*(nY[y+1]-nY[y])*(nZ[z+1]-nZ[z]);
}
int area(int dir) const
{
if(dx[dir]!=0)
return (nY[y+1]-nY[y])*(nZ[z+1]-nZ[z]);
if(dy[dir]!=0)
return (nX[x+1]-nX[x])*(nZ[z+1]-nZ[z]);
return (nX[x+1]-nX[x])*(nY[y+1]-nY[y]);
}
};
void discretize(int a[],int& len)
{
sort(a,a+len);
len = unique(a,a+len)-a;
}
void bfs(int& v,int& s)
{
v=0,s=0;
Cell c;
c.set_vis();
queue<Cell> Q;
Q.push(c);
while(!Q.empty())
{
Cell c=Q.front();
Q.pop();
v+=c.volume();//加上当前空气块的体积
for(int i=0;i<6;i++)
{
Cell tmp = c.neighbor(i);
if(!tmp.valid())//越界
continue;
if(tmp.solid())//是砖块
{
s+=c.area(i);
continue;
}
if(!tmp.get_vis())//没遍历过的空气
{
tmp.set_vis();
Q.push(tmp);
}
}
}
v=1001*1001*1001-v;
}
int main()
{
ios::sync_with_stdio(false);
cin>>t;
while(t--)
{
cin>>n;
memset(X1,0,sizeof(X1));
memset(X2,0,sizeof(X2));
memset(Y1,0,sizeof(Y1));
memset(Y2,0,sizeof(Y2));
memset(Z1,0,sizeof(Z2));
memset(Z2,0,sizeof(Z2));
memset(nX,0,sizeof(nX));
memset(nY,0,sizeof(nY));
memset(nZ,0,sizeof(nZ));
memset(xMark,0,sizeof(xMark));
memset(yMark,0,sizeof(yMark));
memset(zMark,0,sizeof(zMark));
nx=ny=nz=2;
nX[0]=nY[0]=nZ[0]=0;
nX[0]=nY[0]=nZ[0]=1001;
memset(color,0,sizeof(color));
for(int i=0;i<n;i++)
{
cin>>X1[i]>>Y1[i]>>Z1[i]>>X2[i]>>Y2[i]>>Z2[i];
X2[i]+=X1[i];
Y2[i]+=Y1[i];
Z2[i]+=Z1[i];
nX[nx++]=X1[i];nX[nx++]=X2[i];
nY[ny++]=Y1[i];nY[ny++]=Y2[i];
nZ[nz++]=Z1[i];nZ[nz++]=Z2[i];
}
discretize(nX,nx);
for(int i=0;i<nx;i++)
xMark[nX[i]]=i;
discretize(nY,ny);
for(int i=0;i<ny;i++)
yMark[nY[i]]=i;
discretize(nZ,nz);
for(int i=0;i<nz;i++)
zMark[nZ[i]]=i;
for(int i=0;i<n;i++)
{
int x1=xMark[X1[i]];int x2=xMark[X2[i]];
int y1=yMark[Y1[i]];int y2=yMark[Y2[i]];
int z1=zMark[Z1[i]];int z2=zMark[Z2[i]];
for(int x=x1;x<x2;x++)
{
for(int y=y1;y<y2;y++)
{
for(int z=z1;z<z2;z++)
color[x][y][z]=1;
}
}
}
int v,s;
bfs(v,s);
cout<<s<<" "<<v<<endl;
}
return 0;
}
解答：
紫书上的例题，雕塑可能出现包含的情况，即大的雕塑当中可能会内部嵌套一个小的雕塑，外部大的雕塑可能有空洞使得小雕塑与外部连通，也有可能大的雕塑完全封闭住小的雕塑，被完全封在大雕塑内的小雕塑不计算体积与表面积。
书中介绍的方法很巧妙，不非直接遍历雕塑的砖块计算体积与面积，而是转而计算雕塑周围的空气。首先将空间离散化为单位1的格子，使用广搜遍历空气的单位格子，计算空气单位格子6个面邻接的平面是否是砖块，如果是砖块则计算面积，最后得到的总面积就是雕塑的表面积，这种方法不用考虑嵌套与联通的问题。
最后将空间的总体积减去空气的总体积就是就是雕塑的体积。
雕塑的坐标点从1到500，计算时在x轴y轴以及z轴多加一行，方便起始时以（0,0,0）点作为起点计算，最后总体积是1001×1001×1001