UVa 12171 雕塑 sculptures （Sculpture）
发布时间
阅读量：
阅读量
某雕塑由n个边平行于坐标轴的长方体构成。每个长方体通过六个整数参数x, y, z, x₀, y₀, z₀进行定义（其中x₀表示该长方体所有顶点中x坐标值的最小值），这些参数均为1至500之间的整数，并且满足以下条件：
- 长度：在x方向上的长度为(x - x₀)；
- 宽度：在y方向上的长度为(y - y₀)；
- 高度：在z方向上的长度为(z - z₀)；
其他维度同理定义。我们的目标是计算这个雕塑整体所占的空间及其表面积，并对可能存在的情况进行特殊处理：如果存在嵌套情况（即某一个长方体内完全包裹另一个长方体），则不计入额外体积；此外需要注意的是，在整个雕塑结构中可能存在多个独立的部分构成整体形状
要点
- 在存在嵌套结构的情况下，默认仅凭体积计算总体积是不够准确的。
- 物体可能由多个连通块组成，在这种情况下单纯依据体积计算整体积是不合理的。
- 那么该怎么办呢？
- 在解决这个问题之前，请考虑另一个相关问题：该题输入的六个整数均为1-500范围内的数值，在这种情况下我们需要建立一个足够大的三维网格来记录每个长方体的具体位置（假设每个网格单元大小为1x1x1）。然而，在这种情况下（即网格单元数达到约十亿级别），内存不足与程序运行效率均难以满足要求；因此必须采用离散化的方法进行处理。
- 这道题还有一个前提条件：最多只有50个长方体存在；这表明在整个空间中最多只会有大约一百个不同的坐标点（即x、y、z轴上各约一百个不同的取值）。因此我们可以对这些坐标点进行去重并赋予唯一ID值（通过为每个唯一的坐标分配一个唯一的ID值，则整个空间被划分为一个1e6个单元的三维数组）。
- 接下来我们需要做的工作是：建立这样一个1e6规模的空间模型，并在此模型中模拟长方体的存在与分布情况。
- 具体来说：我们将在三维空间中构建一个1e3 \times 1e3 \times 1e3的空间网格；其中每一个单位立方体被视为独立的一个实体（即每个单位立方体占据的空间被视为独立的一个"长方体"）。为了简化计算过程，在这里我们将使用单位立方体中心点来代表整个单位立方体内的情况：如果外部环境存在空气层，则将其视为包围在这些连通块外围的一层空隙区域；这样我们就可以将问题转化为从空气层进入具体物体表面的情况进行分析。
- 最后需要注意的是：当我们在网格中移动时每一步都会产生一定的表面积变化；而总体积可以通过计算移动路径所覆盖的所有单位立方体的数量来确定；最终所求出的空间总体积减去移动路径占用的部分即为我们关心的真实物体体积。
以下是代码
#include<bits/stdc++.h>
using namespace std;
const int maxn = 100 + 10;
const int maxc = 1000 + 30;
int nx, ny, nz, n;
int x[maxn], y[maxn], z[maxn];
int x0[maxn], Y0[maxn], z0[maxn];
int xs[maxn], ys[maxn], zs[maxn];
int color[maxn][maxn][maxn];
//三维图形的六个可移动方向
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 xId, yId, zId;
cell(int x, int y, int z) :xId(x), yId(y), zId(z) {};
};
int getVolume(int xId, int yId, int zId) {
return (xs[xId + 1] - xs[xId]) * (ys[yId + 1] - ys[yId]) *
(zs[zId + 1] - zs[zId]);
}
int getArea(int xId, int yId, int zId, int direction) {
if (dx[direction] != 0) return (ys[yId + 1] - ys[yId]) * (zs[zId + 1] - zs[zId]);
if (dy[direction] != 0) return (zs[zId + 1] - zs[zId]) * (xs[xId + 1] - xs[xId]);
if (dz[direction] != 0) return (xs[xId + 1] - xs[xId]) * (ys[yId + 1] - ys[yId]);
}
//
/*离散化*/
void discretization(int* a, int& n) {
sort(a, a + n);
n = unique(a, a + n) - a;
}
int getId(int* a, int n, int k) {
return lower_bound(a, a + n, k) - a;
}
/*种子填充*/
void floodfill(int& v, int& s) {
queue<cell> q;
q.push(cell(0, 0, 0));
//标记走过
color[0][0][0] = 2;
while (!q.empty()) {
cell c = q.front();
q.pop();
int div = getVolume(c.xId, c.yId, c.zId);
v += getVolume(c.xId, c.yId, c.zId);
for (int i = 0; i < 6; i++) {
cell c2(c.xId + dx[i], c.yId + dy[i], c.zId + dz[i]);
if (c2.xId < 0 || c2.xId > nx - 2 || c2.yId < 0 ||
c2.yId > ny - 2 || c2.zId < 0 || c2.zId > nz - 2)
continue;
if (color[c2.xId][c2.yId][c2.zId] == 1) {
s += getArea(c2.xId, c2.yId, c2.zId, i);
}
else if (!color[c2.xId][c2.yId][c2.zId]) {
color[c2.xId][c2.yId][c2.zId] = 2;
q.push(c2);
}
}
}
int k = v;
v = maxc * maxc * maxc - v;
}
int main() {
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(0);
int T;
cin >> T;
while (T--) {
cin >> n;
//围空气
xs[0] = ys[0] = zs[0] = 0;
xs[1] = ys[1] = zs[1] = maxc;
nx = ny = nz = 2;
//离散化
for (int i = 0; i < n; i++) {
cin >> x[i] >> y[i] >> z[i];
cin >> x0[i] >> Y0[i] >> z0[i];
xs[nx++] = x[i];
xs[nx++] = x[i] + x0[i];
ys[ny++] = y[i];
ys[ny++] = y[i] + Y0[i];
zs[nz++] = z[i];
zs[nz++] = z[i] + z0[i];
}
discretization(xs, nx);
discretization(ys, ny);
discretization(zs, nz);
//转ID， 找被围区域
std::memset(color, 0, sizeof(color));
for (int i = 0; i < n; i++) {
int xIdF = getId(xs, nx, x[i]);
int xIdE = getId(xs, nx, x[i] + x0[i]);
int yIdF = getId(ys, ny, y[i]);
int yIdE = getId(ys, ny, y[i] + Y0[i]);
int zIdF = getId(zs, nz, z[i]);
int zIdE = getId(zs, nz, z[i] + z0[i]);
for (int x = xIdF; x < xIdE; x++) {
for (int y = yIdF; y < yIdE; y++) {
for (int z = zIdF; z < zIdE; z++) {
color[x][y][z] = 1;
}
}
}
}
int v = 0;
int s = 0;
floodfill(v, s);
cout << s << " " << v << endl;
}
}
cpp
全部评论 (0)
还没有任何评论哟~