题意:求被三个或三个以上立方体重合的体积
分析:就是平面面积的加强,不过归根还是一样的,可以把z轴按照从小向大分区间N个,然后可以得到N个平面,用平面重复三次以上的在和高度计算体积。
************************************************************************
#include<stdio.h>
#include<algorithm>
using namespace std; #define Lson r<<1
#define Rson r<<1|1 const int MAXN = ; struct Edge{int x, y1, y2, dir;}e[MAXN];
struct point{int x1,x2, y1,y2, z1,z2;}p[MAXN];
struct segmentTree
{///cover 表示覆盖的次数
int L, R, cover;
long long len1, len2, len3;
int Mid(){return (L+R)>>;}
}a[MAXN<<];
int Hash_Y[MAXN], ny, Hash_Z[MAXN], nz; bool cmp(Edge n1, Edge n2)
{
return n1.x < n2.x;
}
int FindSegLen(int y1, int y2)
{
return Hash_Y[y2] - Hash_Y[y1];
}
void BuildTree(int r, int L, int R)
{
a[r].L = L, a[r].R = R;
a[r].len1 = a[r].len2 = a[r].len3 = a[r].cover = ; if(L == R-)return ; BuildTree(Lson, L, a[r].Mid());
BuildTree(Rson, a[r].Mid(), R);
}
void PushUp(int r)
{///合并,注意要最大区间更新
if( a[r].cover > )
a[r].len1 = a[r].len2 = a[r].len3 = FindSegLen( a[r].L, a[r].R );
else if( a[r].L == a[r].R- && a[r].cover == )
a[r].len3 = , a[r].len2 = a[r].len1 = FindSegLen( a[r].L, a[r].R );
else if( a[r].L == a[r].R- && a[r].cover == )
a[r].len3 = a[r].len2 = , a[r].len1 = FindSegLen( a[r].L, a[r].R );
else if( a[r].L == a[r].R- )
a[r].len1 = a[r].len2 = a[r].len3 = ;
else if( a[r].cover == )
{
a[r].len3 = a[Lson].len1 + a[Rson].len1;
a[r].len2 = a[r].len1 = FindSegLen( a[r].L, a[r].R );;
}
else if( a[r].cover == )
{
a[r].len3 = a[Lson].len2 + a[Rson].len2;
a[r].len2 = a[Lson].len1 + a[Rson].len1;
a[r].len1 = FindSegLen( a[r].L, a[r].R );
}
else
{
a[r].len3 = a[Lson].len3 + a[Rson].len3;
a[r].len2 = a[Lson].len2 + a[Rson].len2;
a[r].len1 = a[Lson].len1 + a[Rson].len1;
}
}
void UpData(int r, int L, int R, int dir)
{
if( a[r].L == L && a[r].R == R )
{
a[r].cover += dir;
PushUp(r); return ;
} if(R <= a[r].Mid())
UpData(Lson, L, R, dir);
else if(L >= a[r].Mid())
UpData(Rson, L, R, dir);
else
{
UpData(Lson, L, a[r].Mid(), dir);
UpData(Rson, a[r].Mid(), R, dir);
} PushUp(r);
} int main()
{
int T, t=; scanf("%d", &T); while(T--)
{
int i, j, k, N;
long long V=; scanf("%d", &N); for(nz=i=; i<N; i++)
{
scanf("%d%d%d%d%d%d", &p[i].x1,&p[i].y1,&p[i].z1,&p[i].x2,&p[i].y2,&p[i].z2);
Hash_Z[nz++] = p[i].z1, Hash_Z[nz++] = p[i].z2;
} sort(Hash_Z, Hash_Z+nz);
nz = unique(Hash_Z, Hash_Z+nz) - Hash_Z; for(i=; i<nz-; i++)
{///以z轴底部开始,判断每层是否有三个区间重合的
for(ny=k=j=; j<N; j++)
{
if( Hash_Z[i] >= p[j].z1 && Hash_Z[i] < p[j].z2 )
{
e[k].x=p[j].x1, e[k].y1=p[j].y1, e[k].y2=p[j].y2, e[k++].dir=;
e[k].x=p[j].x2, e[k].y1=p[j].y1, e[k].y2=p[j].y2, e[k++].dir=-;
Hash_Y[ny++] = p[j].y1, Hash_Y[ny++] = p[j].y2;
}
} sort(Hash_Y, Hash_Y+ny);
ny = unique(Hash_Y, Hash_Y+ny)-Hash_Y;
BuildTree(, , ny-); sort(e, e+k, cmp); long long S = ; for(j=; j<k-; j++)
{
int L = lower_bound(Hash_Y, Hash_Y+ny, e[j].y1) - Hash_Y;
int R = lower_bound(Hash_Y, Hash_Y+ny, e[j].y2) - Hash_Y; UpData(, L, R, e[j].dir); S += (long long)a[].len3 * ( e[j+].x - e[j].x );
} V += S * (Hash_Z[i+] - Hash_Z[i]);
} printf("Case %d: %lld\n", t++, V);
} return ;
}