UVa 737 Gleaming the Cubes

题目描述给定若干个轴对齐的立方体每个立方体由其一个角点坐标(x,y,z)(x,y,z)(x,y,z)和边长sss向三个轴正方向延伸定义。需要计算所有这些立方体的交集部分的体积。输入包含多组数据每组数据先给出立方体个数nnn2≤n≤10002 \le n \le 10002≤n≤1000随后nnn行每行四个整数x,y,z,sx,y,z,sx,y,z,s。输出交集体积若交集为空则输出000。所有交集体积不超过10610^6106。输入格式输入包含多组测试数据。每组数据第一行为一个整数nnn表示立方体个数。随后nnn行每行四个整数x,y,z,sx,y,z,sx,y,z,s分别表示角点坐标和边长。输入以n0n 0n0结束。输出格式对于每组数据输出一行包含一个整数即所有立方体的交集体积。样例输入2 0 0 0 10 9 1 1 5 3 0 0 0 10 9 1 1 5 8 2 2 3 0样例输出25 9题目分析每个立方体是轴对齐的其内部点集可表示为[x1,x2]×[y1,y2]×[z1,z2] [x_1, x_2] \times [y_1, y_2] \times [z_1, z_2][x1​,x2​]×[y1​,y2​]×[z1​,z2​]其中x2x1sx_2 x_1 sx2​x1​sy2y1sy_2 y_1 sy2​y1​sz2z1sz_2 z_1 sz2​z1​s。多个立方体的交集仍然是轴对齐长方体可能为空其各坐标范围分别为所有立方体对应区间下界的最大值和上界的最小值。即Xlowmax⁡ix1i,Xupmin⁡ix2i X_{\text{low}} \max_i x_{1i},\quad X_{\text{up}} \min_i x_{2i}Xlow​imax​x1i​,Xup​imin​x2i​YYY和ZZZ方向同理。若任一方向满足Xlow≥XupX_{\text{low}} \ge X_{\text{up}}Xlow​≥Xup​或YYY或ZZZ则交集为空体积为000否则体积为(Xup−Xlow)×(Yup−Ylow)×(Zup−Zlow)(X_{\text{up}} - X_{\text{low}}) \times (Y_{\text{up}} - Y_{\text{low}}) \times (Z_{\text{up}} - Z_{\text{low}})(Xup​−Xlow​)×(Yup​−Ylow​)×(Zup​−Zlow​)。解题思路算法步骤确定如下步骤1\texttt{1}1. 读入nnn若n0n0n0则终止。步骤2\texttt{2}2. 读入第一个立方体的角点坐标(x1,y1,z1)(x_1,y_1,z_1)(x1​,y1​,z1​)和边长sss计算其两个对角点坐标(x2,y2,z2)(x1s,y1s,z1s)(x_2,y_2,z_2) (x_1s, y_1s, z_1s)(x2​,y2​,z2​)(x1​s,y1​s,z1​s)并初始化交集的下界lowxx1\text{low}x x_1lowxx1​、lowyy1\text{low}y y_1lowyy1​、lowzz1\text{low}z z_1lowzz1​上界upxx2\text{up}x x_2upxx2​、upyy2\text{up}y y_2upyy2​、upzz2\text{up}z z_2upzz2​。步骤3\texttt{3}3. 对于后续每个立方体读入其角点和边长计算其二对角点然后更新lowxmax⁡(lowx,x1)\text{low}x \max(\text{low}x, x_1)lowxmax(lowx,x1​)lowymax⁡(lowy,y1)\text{low}y \max(\text{low}y, y_1)lowymax(lowy,y1​)lowzmax⁡(lowz,z1)\text{low}z \max(\text{low}z, z_1)lowzmax(lowz,z1​)upxmin⁡(upx,x2)\text{up}x \min(\text{up}x, x_2)upxmin(upx,x2​)upymin⁡(upy,y2)\text{up}y \min(\text{up}y, y_2)upymin(upy,y2​)upzmin⁡(upz,z2)\text{up}z \min(\text{up}z, z_2)upzmin(upz,z2​)步骤4\texttt{4}4. 若lowx≥upx\text{low}x \ge \text{up}xlowx≥upx或lowy≥upy\text{low}y \ge \text{up}ylowy≥upy或lowz≥upz\text{low}z \ge \text{up}zlowz≥upz则交集体积为000否则计算体积并输出。该算法时间复杂度O(n)O(n)O(n)空间复杂度O(1)O(1)O(1)完全满足n≤1000n \le 1000n≤1000的限制。代码实现// Gleaming the Cubes// UVa ID: 737// Verdict: Accepted// Submission Date: 2017-12-18// UVa Run Time: 0.010s//// 版权所有C2017邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;structcube{intx1,y1,z1,x2,y2,z2;}cubes[1010];intmain(intargc,char*argv[]){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);intn,r;while(cinn,n0){for(inti0;in;i){cincubes[i].x1cubes[i].y1cubes[i].z1r;cubes[i].x2cubes[i].x1r;cubes[i].y2cubes[i].y1r;cubes[i].z2cubes[i].z1r;}intlowxcubes[0].x1,lowycubes[0].y1,lowzcubes[0].z1;intupxcubes[0].x2,upycubes[0].y2,upzcubes[0].z2;for(inti1;in;i){lowxmax(lowx,cubes[i].x1);lowymax(lowy,cubes[i].y1);lowzmax(lowz,cubes[i].z1);upxmin(upx,cubes[i].x2);upymin(upy,cubes[i].y2);upzmin(upz,cubes[i].z2);}if(lowxupx||lowyupy||lowzupz)cout0\n;elsecout(upx-lowx)*(upy-lowy)*(upz-lowz)\n;}return0;}总结本题通过简单维护各坐标轴方向上的区间交集直接计算出所有立方体公共部分的体积。由于立方体轴对齐区间交集的特性使得问题退化为求多个区间的交集避免了复杂的三维几何计算。代码实现清晰时间复杂度线性空间常数。关键在于理解立方体交集体积等于各方向区间长度乘积以及当任意方向区间为空时体积为零。该解法可推广到更高维度的轴对齐超长方体交集问题。