题意：给出在三维空间的一些立方体。这些立方体可能会重叠，包含。求出这些立方体的体积并和表面积。需要注意的一点：这些立方体的组合会产生空腔，而空腔也算体积的一部分，同时，从外部看不到的面也不计算表面积。 思路：这个题目中的关键词就是外部：体积是从外部计算的，空腔也只算外表面的。所以我们要从外部算起。           floodfill算法中，我们不仅能统计连通块的个数，还能统计连通块的面积、体积，甚至边长、面积。           这样，我们向外扩充一圈空气，求出空气的体积和空气的内表面积，就可以间接的求出这些立方体的体积和表面积了。           但是,floodfill就是bfs/dfs，题中可能会有500*500*500的节点，这样非常有可能会TLE。           所以，我们需要对原来的坐标进行离散化。但是在统计体积和面积的时候，还是要用原来的坐标。 注意：在反离散化时，如何用离散化后的坐标来求离散化前的坐标，当时想了很多方法，都没有好的解决方法。这里，较好的处理技巧就是少填充一个，每个点对应一个线段，这样，我们就能计算原来的面积和体积了。            还有一点的是：不能用x0,y0,x1,y1,这些变量已经被库函数用了，要是用这些变量的话，会出现CE

代码如下： #include #include #include #include using namespace std; const int MAXN = 55; const int MAXC = 1001; 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 point{ int x,y,z; point(int xx,int yy, int zz):x(xx),y(yy),z(zz){} }; int T,N; int s,v; int nx,ny,nz; int xx0[MAXN],xx1[MAXN],yy0[MAXN],yy1[MAXN],z0[MAXN],z1[MAXN]; int xs[MAXN<<2],ys[MAXN<<2],zs[MAXN<<2]; int color[MAXN<<2][MAXN<<2][MAXN<<2]; void init() { nx = ny = nz = v = s = 0; memset(color,0,sizeof(color)); } int area(int x,int y,int z,int dir) { if(dx[dir] != 0) return (ys[y+1] - ys[y]) * (zs[z+1] - zs[z]); else if(dy[dir] != 0) return (xs[x+1] - xs[x]) * (zs[z+1] - zs[z]); else return (xs[x+1] - xs[x]) * (ys[y+1] - ys[y]); } void bfs() { queue Q; Q.push(point(0,0,0)); color[0][0][0] = 2; while(!Q.empty()){ point t = Q.front();Q.pop(); printf("%d %d ",s,v); v += (xs[t.x + 1] - xs[t.x]) * (ys[t.y + 1] - ys[t.y]) * (zs[t.z + 1] - zs[t.z]); for(int i = 0; i < 6; ++i){ int x = t.x + dx[i], y = t.y + dy[i], z = t.z + dz[i]; if(x >= 0 && x < nx -1 && y >= 0 && y < ny -1 && z >= 0 && z < nz - 1){ if(color[x][y][z] == 1) s += area(x,y,z,i); else if(color[x][y][z] == 0){ color[x][y][z] = 2; Q.push(point(x,y,z)); } } } } v = MAXC * MAXC * MAXC - v; } int main(void) { //freopen("input.txt","r",stdin); //freopen("out.txt","w",stdout); scanf("%d", &T); while(T--){ scanf("%d", &N); init(); xs[nx++] = 0; ys[ny++] = 0; zs[nz++] = 0; xs[nx++] = MAXC;ys[ny++] = MAXC;zs[nz++] = MAXC; for(int i = 0; i < N; ++i){ scanf("%d %d %d %d %d %d",&xx0[i],&yy0[i],&z0[i],&xx1[i],&yy1[i],&z1[i]); xx1[i] += xx0[i];yy1[i] += yy0[i];z1[i] += z0[i]; xs[nx++] = xx0[i];xs[nx++] = xx1[i]; ys[ny++] = yy0[i];ys[ny++] = yy1[i]; zs[nz++] = z0[i];zs[nz++] = z1[i]; } sort(xs,xs + nx); sort(ys,ys + ny); sort(zs,zs + nz); nx = unique(xs,xs + nx) - xs; ny = unique(ys,ys + ny) - ys; nz = unique(zs,zs + nz) - zs; for(int i = 0; i < N; ++i){ int X0 = lower_bound(xs,xs + nx,xx0[i]) - xs; int X1 = lower_bound(xs,xs + nx,xx1[i]) - xs; int Y0 = lower_bound(ys,ys + ny,yy0[i]) - ys; int Y1 = lower_bound(ys,ys + ny,yy1[i]) - ys; int Z0 = lower_bound(zs,zs + nz,z0[i]) - zs; int Z1 = lower_bound(zs,zs + nz,z1[i]) - zs; for(int x = X0; x < X1; ++x) for(int y = Y0; y < Y1; ++y) for(int z = Z0; z < Z1; ++z) color[x][y][z] = 1; } bfs(); printf("%d %d ",s,v); } return 0; }