题目链接：https://vjudge.net/problem/HDU-3642
Jack knows that there is a great underground treasury in a secret region. And he has a special device that can be used to detect treasury under the surface of the earth. One day he got outside with the device to ascertain the treasury. He chose many different locations on the surface of the earth near the secret region. And at each spot he used the device to detect treasury and got some data from it representing a region, which may contain treasury below the surface. The data from the device at each spot is six integers x 1, y 1, z 1, x 2, y 2 and z 2 (x 1<x 2, y 1<y 2, z 1<z 2). According to the instruction of the device they represent the range of x, y and z coordinates of the region. That is to say, the x coordinate of the region, which may contain treasury, ranges from x 1 to x 2. So do y and z coordinates. The origin of the coordinates is a fixed point under the ground.
Jack can’t get the total volume of the treasury because these regions don’t always contain treasury. Through years of experience, he discovers that if a region is detected that may have treasury at more than two different spots, the region really exist treasure. And now Jack only wants to know the minimum volume of the treasury.
Now Jack entrusts the problem to you.
Jack can’t get the total volume of the treasury because these regions don’t always contain treasury. Through years of experience, he discovers that if a region is detected that may have treasury at more than two different spots, the region really exist treasure. And now Jack only wants to know the minimum volume of the treasury.
Now Jack entrusts the problem to you.
InputThe first line of the input file contains a single integer t, the number of test cases, followed by the input data for each test case.
Each test case is given in some lines. In the first line there is an integer n (1 ≤ n ≤ 1000), the number of spots on the surface of the earth that he had detected. Then n lines follow, every line contains six integers x 1, y 1, z 1, x 2, y 2 and z2, separated by a space. The absolute value of x and y coordinates of the vertices is no more than 10 6, and that of z coordinate is no more than 500.
OutputFor each test case, you should output “Case a: b” in a single line. a is the case number, and b is the minimum volume of treasury. The case number is counted from one.
Sample Input
2 1 0 0 0 5 6 4 3 0 0 0 5 5 5 3 3 3 9 10 11 3 3 3 13 20 45
Sample Output
Case 1: 0 Case 2: 8
代码如下：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <algorithm> 6 #include <vector> 7 #include <queue> 8 #include <stack> 9 #include <map> 10 #include <string> 11 #include <set> 12 using namespace std; 13 typedef long long LL; 14 const double EPS = 1e-8; 15 const int INF = 2e9; 16 const LL LNF = 2e18; 17 const int MAXN = 1e3+10; 18 19 int times[MAXN<<3]; //times为该区间被覆盖的次数 20 int one[MAXN<<3], two[MAXN<<3], more[MAXN<<3]; 21 int Z[MAXN<<1], X[MAXN<<1]; //Z、X分别用于离散化Z坐标和X坐标 22 23 struct Cube 24 { 25 int x1, y1, z1,x2, y2, z2; 26 }cube[MAXN]; 27 28 struct Line 29 { 30 int le, ri, h, id; 31 bool operator<(const Line &a)const{ 32 return h<a.h; 33 } 34 35 }line[MAXN<<1]; 36 37 void push_up(int u, int l, int r) 38 { 39 if(times[u]>=3) //该区间被覆盖三次 40 { 41 more[u] = X[r] - X[l]; 42 two[u] = X[r] - X[l]; 43 one[u] = X[r] - X[l]; 44 } 45 else if(times[u]==2) //两次 46 { 47 more[u] = (l+1==r)?0:(one[u*2]+one[u*2+1]); 48 two[u] = X[r] - X[l]; 49 one[u] = X[r] - X[l]; 50 } 51 else if(times[u]==1) //一次 52 { 53 more[u] = (l+1==r)?0:(two[u*2]+two[u*2+1]); 54 two[u] = (l+1==r)?0:(one[u*2]+one[u*2+1]); 55 one[u] = X[r] - X[l]; 56 } 57 else //没有被覆盖 58 { 59 more[u] = (l+1==r)?0:(more[u*2]+more[u*2+1]); 60 two[u] = (l+1==r)?0:(two[u*2]+two[u*2+1]); 61 one[u] = (l+1==r)?0:(one[u*2]+one[u*2+1]); 62 } 63 } 64 65 //此种线段树的操作对象为连续型，即最小的元素为长度为1的区间[l,r],其中l和r只代表端点(r-l>=1)，用于确定 66 //区间的位置和长度，l和r本身没有特别的含义。而以往做的什么单点更新之类的，都属于离散型，在l处和r处是有含义的 67 void add(int u, int l, int r, int x, int y, int v) 68 { 69 if(x<=l && r<=y) 70 { 71 times[u] += v; 72 push_up(u, l, r); 73 return; 74 } 75 76 int mid = (l+r)>>1; 77 if(x<=mid-1) add(u*2, l, mid, x, y, v); 78 if(y>=mid+1) add(u*2+1, mid, r, x, y, v); 79 push_up(u, l, r); 80 } 81 82 int main() 83 { 84 int T, n; 85 scanf("%d", &T); 86 for(int kase = 1; kase<=T; kase++) 87 { 88 scanf("%d", &n); 89 int numZ = 0; 90 for(int i = 1; i<=n; i++) 91 { 92 scanf("%d%d%d", &cube[i].x1,&cube[i].y1,&cube[i].z1); 93 scanf("%d%d%d", &cube[i].x2,&cube[i].y2,&cube[i].z2); 94 Z[++numZ] = cube[i].z1; Z[++numZ] = cube[i].z2; 95 } 96 97 sort(Z+1, Z+1+numZ); //离散化Z坐标 98 numZ = unique(Z+1, Z+1+numZ) - (Z+1); 99 100 LL volume = 0; 101 for(int i = 1; i<numZ; i++) //枚举每一个平面（平面垂直于Z轴） 102 { 103 int numLine = 0, numX = 0; 104 for(int j = 1; j<=n; j++) 105 if(cube[j].z1<=Z[i] && Z[i+1]<=cube[j].z2) //获得在此平面有效的长方体，然后保存他们在此平面的上下边。 106 { 107 line[++numLine].le = cube[j].x1; line[numLine].ri = cube[j].x2; 108 line[numLine].h = cube[j].y1; line[numLine].id = 1; 109 line[++numLine].le = cube[j].x1; line[numLine].ri = cube[j].x2; 110 line[numLine].h = cube[j].y2; line[numLine].id = -1; 111 X[++numX] = cube[j].x1; X[++numX] = cube[j].x2; 112 } 113 114 sort(line+1, line+1+numLine); //在此平面中，根据高度（即y坐标）对线段进行排序 115 sort(X+1, X+1+numX); 116 numX = unique(X+1, X+1+numX) - (X+1); //离散化X坐标 117 118 memset(times, 0, sizeof(times)); 119 memset(more, 0, sizeof(more)); 120 memset(two, 0, sizeof(two)); 121 memset(one, 0, sizeof(one)); 122 123 LL area = 0; 124 for(int j = 1; j<numLine; j++) //计算此平面的有效面积 125 { 126 int l = upper_bound(X+1, X+1+numX, line[j].le) - (X+1); 127 int r = upper_bound(X+1, X+1+numX, line[j].ri) - (X+1); 128 add(1, 1, numX, l, r, line[j].id); 129 area += 1LL*more[1]*(line[j+1].h-line[j].h); 130 } 131 volume += 1LL*area*(Z[i+1]-Z[i]); //计算两个平面之间的体积，然后再累加 132 } 133 printf("Case %d: %lld ", kase, volume); 134 } 135 }