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 x1 to x2. 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 x1, y1, z1,
x2, y2 and z2, separated by a space. The absolute value of x and y coordinates of the vertices is no more than 106, 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 h2) {
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+1]-x[l];
else if(l==r)
twice[rt]=0;
else if(cnt[rt]==1)
twice[rt]=once[rt<<1]+once[rt<<1|1];
else
twice[rt]=twice[rt<<1]+twice[rt<<1|1];
if(cnt[rt]>2)
more[rt]=x[r+1]-x[l];
else if(l==r)
more[rt]=0;
else if(cnt[rt]==2)
more[rt]=once[rt<<1]+once[rt<<1|1];
else if(cnt[rt]==1)
more[rt]=twice[rt<<1]+twice[rt<<1|1];
else
more[rt]=more[rt<<1]+more[rt<<1|1];
}
void update(int L,int R,int c,int l,int r,int rt)
{
if(L<=l&&r<=R) {
cnt[rt]+=c;
push_up(rt,l,r);
return ;
}
int m=(l+r)>>1;
if(L<=m) update(L,R,c,lson);
if(mz[i]){
int x1=cube[j].a.x,x2=cube[j].b.x;
int y1=cube[j].a.y,y2=cube[j].b.y;
ss[tot++]=Seg(x1,x2,y1,1);
ss[tot++]=Seg(x1,x2,y2,-1);
}
}sort(ss,ss+tot);
memset(cnt,0,sizeof(cnt));
memset(once,0,sizeof(once));
memset(twice,0,sizeof(twice));
memset(more,0,sizeof(more));
for(int j=0;j>T;
while(T--){
int m=0;
cin>>n;
while(n--){
cube[m].a.get();
x[m<<1]=cube[m].a.x,z[m<<1]=cube[m].a.z;
cube[m].b.get();
x[m<<1|1]=cube[m].b.x,z[m<<1|1]=cube[m].b.z;
m++;
}
printf("Case %d: ",cas++);
solve(m);
}
return 0;
}
