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.
Input The 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 z
2, 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.
Output For 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
――――――――――――――――――――――
分割线――――――――――――――――――
题目大意：
给定n个长方体，求体积交3次及以上的体积和
思路：
将长方体投影到XOY平面，那么就转化为求面积交3次及以上，只要对z进行排序，枚举z，每次找出平面在z+1和z之间的平面，求面积并3次及以上
更新操作写了两种：
第一种：
1：once[]覆盖1次，twice[]覆盖2次，more[]覆盖2次以上
2：覆盖1次+覆盖2次+覆盖3次=区间长度 once[]+twice[]+more[]=len
3：那么once，twice，more是互不包含的
如果cnt>2那么more等于区间长度
如果cnt==2，那么more=左右儿子中 twice（4次）+once（3次）+more（3次及以上）；
如果cnt==1，那么more=左右儿子中 twice（3次）+ more（3次及以上）；
如果cnt==0，则当前节点表示的区间没有被完全覆盖，则once，twice，more应该由他们的左右子树得到
第二种：
1：once[]覆盖1次及以上，twice[]覆盖2次及以上，more[]覆盖3次及以上
2：more包含twice和once，twice包含once
3：once，twice，more分开更新
对于once{]的更新：
如果cnt存在，则once[]=区间长度；
否则如果没有被覆盖又是叶子节点，once=0；
否则如果既没有被完全覆盖又不是叶子节点，则由它的左右子树得到；
对于twice[]的更新：
如果cnt>1，则twice[]=区间长度；
否则如果没有被覆盖1次以上又是叶子节点，twice=0；
否则如果cnt==1，twice=左右子树中 的once
否则如果cnt==0，twice由左右子树得到
对于more[]的更新：
如果cnt>2，则more[]=区间长度；
否则如果没有被覆盖2次以上，more=0；
否则如果cnt==2，more=左右子树once的和（不需要加上twice，因为once包含twice）
否则如果cnt==1，more=左右子树twice的和（不需要加上once）
否则如果cnt==0，则more应由左右子树得到
#include
#include
#include
#include
#define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define ll long long const int maxn=2222; using namespace std; int cnt[maxn<<2],x[maxn],z[maxn]; int once[maxn<<2],twice[maxn<<2],more[maxn<<2]; struct point{ int x,y,z; void get(){ scanf("%d %d %d",&x,&y,&z); } }; struct Cube{ point a,b; }cube[maxn]; struct Seg { int l,r,h; int s; Seg(){}; Seg(int a,int b,int c,int d):l(a),r(b),h(c),s(d){}; bool operator<(const Seg&cmp)const{ return h
2) { more[rt]=x[r+1]-x[l]; once[rt]=twice[rt]=0; } else if(cnt[rt]==2){ if(l==r) { twice[rt]=x[r+1]-x[l]; once[rt]=more[rt]=0; } else { more[rt]=more[rt<<1]+more[rt<<1|1]+once[rt<<1]+once[rt<<1|1]+twice[rt<<1]+twice[rt<<1|1]; twice[rt]=x[r+1]-x[l]-more[rt]; once[rt]=0; } } else if(cnt[rt]==1) { if(l==r){ once[rt]=x[r+1]-x[l]; twice[rt]=more[rt]=0; } else { more[rt]=more[rt<<1]+more[rt<<1|1]+twice[rt<<1]+twice[rt<<1|1]; twice[rt]=once[rt<<1]+once[rt<<1|1]; once[rt]=x[r+1]-x[l]-twice[rt]-more[rt]; } } else if(cnt[rt]==0){ if(l==r) { once[rt]=twice[rt]=more[rt]=0; } else { once[rt]=once[rt<<1]+once[rt<<1|1]; twice[rt]=twice[rt<<1]+twice[rt<<1|1]; more[rt]=more[rt<<1]+more[rt<<1|1]; } } } */ void push_up(int rt,int l,int r) { if(cnt[rt]) once[rt]=x[r+1]-x[l]; else if(l==r) once[rt]=0; else once[rt]=once[rt<<1]+once[rt<<1|1]; if(cnt[rt]>1) twice[rt]=x[r+