首页 > 代码库 > Light Oj 1211 计算多个立方体重叠部分体积
Light Oj 1211 计算多个立方体重叠部分体积
Intersection of Cubes
Time Limit:500MS Memory Limit:32768KB 64bit IO Format:%lld & %llu
Submit
Status
Practice
LightOJ 1211
Description
You are given n cubes, each cube is described by two points in 3D space: (x1, y1, z1) being one corner of the cube and (x2, y2, z2) being the opposite corner. Assume that the sides of each of the cubes are parallel to the axis. Your task is to find the volume of their intersection.
Input
Input starts with an integer T (≤ 100), denoting the number of test cases.
Each case starts with a line containing an integer n (1 ≤ n ≤ 100). Each of the next n lines contains six integers x1 y1 z1 x2 y2 z2 (1 ≤ x1, y1, z1, x2, y2, z2 ≤ 1000, x1 < x2, y1 < y2, z1 < z2) where (x1, y1, z1) is the co-ordinate of one corner and (x2, y2, z2) is the co-ordinate of the opposite corner.
Output
For each case, print the case number and volume of their intersection.
Sample Input
2
2
1 1 1 3 3 3
1 1 1 2 2 2
3
7 8 9 20 20 30
2 2 2 50 50 50
13 14 15 18 30 40
Sample Output
Case 1: 1
Case 2: 450
<span style="color:#000099;">/********************************************* author : Grant Yuan time : 2014.8.7 algorithm: 计算几何 source : Light Oj 1211 explain : 求几个正方体重叠部分的体积 ***********************************************/ #include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> #define INF 0x3fffffff using namespace std; int t,n,a[7]; int ans; int main() { scanf("%d",&t);int c; for(int i=1;i<=t;i++) { scanf("%d",&n); a[1]=a[2]=a[3]=0; a[4]=a[5]=a[6]=INF; for(int j=1;j<=n;j++) { for(int k=1;k<=3;k++) { scanf("%d",&c); if(c>a[k]) a[k]=c; } for(int k=4;k<=6;k++) { scanf("%d",&c); if(c<a[k]) a[k]=c; } } if(a[4]>a[1]&&a[5]>a[2]&&a[6]>a[3]) { ans=(a[4]-a[1])*(a[5]-a[2])*(a[6]-a[3]); printf("Case %d: %d\n",i,ans);} else printf("Case %d: 0\n",i); } return 0; } </span>