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.
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 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.
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
C++版本一
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <math.h>
#include <vector>
#include <map>
using namespace std;
const int N=10000+10;
int t,n,m,cnt=0;
int tree1[N],tree2[N],tree3[N];
int flag[N];
int y[N],Y[N],Z[N];
map <int ,int >my;
void init(){
memset(tree1,0,sizeof(tree1));
memset(tree2,0,sizeof(tree2));
memset(tree3,0,sizeof(tree3));
memset(flag,0,sizeof(flag));
}
struct Point{
int x,y,z,x2,y2,z2;
}P[N];
struct node{
int l,r,y,s;
node(){};
node(int x,int x2,int y0,int s0){
l=x;
r=x2;
y=y0;
s=s0;
}
bool operator <(const node &S)const{
return y<S.y;
}
}G[N];
void pushup(int i,int l,int r){
if(flag[i]>2){
tree3[i]=Y[r+1]-Y[l];
tree1[i]=tree2[i]=0;
}else if(flag[i]==2){
if(l==r){
tree2[i]=Y[r+1]-Y[l];
tree1[i]=tree3[i]=0;
}else{
tree3[i]=tree1[i<<1]+tree1[i<<1|1]+tree2[i<<1]+tree2[i<<1|1]+tree3[i<<1]+tree3[i<<1|1];
tree2[i]=Y[r+1]-Y[l]-tree3[i];
tree1[i]=0;
}
}else if(flag[i]==1){
if(l==r){
tree1[i]=Y[r+1]-Y[l];
tree2[i]=tree3[i]=0;
}else{
tree3[i]=tree2[i<<1]+tree2[i<<1|1]+tree3[i<<1]+tree3[i<<1|1];
tree2[i]=tree1[i<<1]+tree1[i<<1|1];
tree1[i]=Y[r+1]-Y[l]-tree2[i]-tree3[i];
}
}else if(flag[i]==0){
if(l==r){
tree1[i]=tree2[i]=tree3[i]=0;
}else{
tree3[i]=tree3[i<<1]+tree3[i<<1|1];
tree2[i]=tree2[i<<1]+tree2[i<<1|1];
tree1[i]=tree1[i<<1]+tree1[i<<1|1];
}
}
}
void updata(int i,int l,int r,int L,int R,int C){
if(L<=l&&r<=R){
flag[i]+=C;
pushup(i,l,r);
return;
}
if(l==r) return;
int m=(l+r)/2;
if(L<=m)
updata(i<<1,l,m,L,R,C);
if(m<R)
updata(i<<1|1,m+1,r,L,R,C);
pushup(i,l,r);
}
int main()
{
scanf("%d",&t);
for(int T=1;T<=t;T++){
cnt=0;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d%d%d%d%d%d",&P[i].x,&P[i].y,&P[i].z,&P[i].x2,&P[i].y2,&P[i].z2);
Y[++cnt]=P[i].y;
Z[cnt]=P[i].z;
Y[++cnt]=P[i].y2;
Z[cnt]=P[i].z2;
}
sort(Y+1,Y+cnt+1);
sort(Z+1,Z+cnt+1);
int k=1;
int p=1;
for(int i=2;i<=cnt;i++){
if(Y[i]!=Y[i+1])
Y[++k]=Y[i];
if(Z[i]!=Z[i+1])
Z[++p]=Z[i];
}
init();
for (int i = 1; i <=k; ++i)
my[Y[i]] = i;
long long ans=0;
for(int i=1;i<p;i++){
int c=0;
for(int j=1;j<=n;j++){
if(P[j].z<=Z[i]&&P[j].z2>Z[i]){
G[++c]=node(P[j].y,P[j].y2,P[j].x,1);
G[++c]=node(P[j].y,P[j].y2,P[j].x2,-1);
}
}
sort(G+1,G+c+1);
for(int j=1;j<c;j++){
updata(1,1,k,my[G[j].l],my[G[j].r]-1,G[j].s);
//cout<<ans<<endl;
ans+=(Z[i+1]-Z[i])*(long long)tree3[1]*(G[j+1].y-G[j].y);
}
updata(1,1,k,my[G[c].l],my[G[c].r]-1,G[c].s);
}
printf("Case %d: %lld\n",T,ans);
}
//cout << "Hello world!" << endl;
return 0;
}
C++版本二
给定n个立方体，求这些立方体覆盖两次以上的体积。
之前做过求矩形面积交的题，这题可以转化为求矩形面积交。先对y坐标和z坐标离散化，然后枚举每个z轴区间，求在该区间内矩形覆盖两次以上的面积，再乘以该区间宽度，即为该区间覆盖两次以上的体积。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <map>
using namespace std;
const int maxn = 2010;
int yy[maxn], zz[maxn];
int cov[maxn<<2], once[maxn<<2];
int twice[maxn<<2], more[maxn<<2];
map<int, int> my;
int t, n;
struct Point
{
int x, y, z;
void get()
{
scanf("%d%d%d", &x, &y, &z);
}
};
struct Cube
{
Point a, b;
}cube[maxn];
struct Line
{
int y1, y2, x;
int flag;
}line[maxn];
bool cmp(Line a, Line b)
{
if (a.x != b.x)
return a.x < b.x;
return a.flag > b.flag;
}
void addLine(int y1, int y2, int x, int flag, int idx)
{
line[idx].y1 = y1;
line[idx].y2 = y2;
line[idx].x = x;
line[idx].flag = flag;
}
void build(int l, int r, int rt)
{
cov[rt] = once[rt] = twice[rt] = more[rt] = 0;
if (l + 1 == r) return ;
int m = (l + r) >> 1;
build(l, m, rt << 1);
build(m, r, rt << 1 | 1);
}
void pushUp(int l, int r, int rt)
{
if (cov[rt] > 2)
{
more[rt] = yy[r] - yy[l];
once[rt] = twice[rt] = 0;
return ;
}
if (cov[rt] == 2)
{
if (l + 1 == r)
{
twice[rt] = yy[r] - yy[l];
once[rt] = more[rt] = 0;
}
else
{
more[rt] = more[rt<<1] + more[rt<<1|1] + twice[rt<<1] +
twice[rt<<1|1] + once[rt<<1] + once[rt<<1|1];
twice[rt] = yy[r] - yy[l] - more[rt];
once[rt] = 0;
}
return ;
}
if (cov[rt] == 1)
{
if (l + 1 == r)
{
once[rt] = yy[r] - yy[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] = yy[r] - yy[l] - twice[rt] - more[rt];
}
return ;
}
if (cov[rt] == 0)
{
if (l + 1 == r)
more[rt] = twice[rt] = once[rt] = 0;
else
{
more[rt] = more[rt<<1] + more[rt<<1|1];
twice[rt] = twice[rt<<1] + twice[rt<<1|1];
once[rt] = once[rt<<1] + once[rt<<1|1];
}
return ;
}
}
void update(int L, int R, int c, int l, int r, int rt)
{
if (L <= l && R >= r)
{
cov[rt] += c;
pushUp(l, r, rt);
return ;
}
if (l + 1 == r) return ;
int m = (l + r) >> 1;
if (L < m) update(L, R, c, l, m, rt << 1);
if (R > m) update(L, R, c, m, r, rt << 1 | 1);
pushUp(l, r, rt);
}
void solve()
{
sort(yy, yy + n * 2);
sort(zz, zz + n * 2);
int cnty = 1;
for (int i = 1; i < n * 2; ++i)
{
if (yy[i] != yy[cnty-1])
yy[cnty++] = yy[i];
}
int cntz = 1;
for (int i = 1; i < n * 2; ++i)
{
if (zz[i] != zz[cntz-1])
zz[cntz++] = zz[i];
}
for (int i = 0; i < cnty; ++i)
my[yy[i]] = i;
long long ans = 0;
build(0, cnty - 1, 1);
for (int i = 0; i < cntz - 1; ++i)
{
int cnt = 0;
for (int j = 0; j < n; ++j)
{
if (cube[j].a.z <= zz[i] && cube[j].b.z > zz[i])
{
addLine(cube[j].a.y, cube[j].b.y, cube[j].a.x, 1, cnt++);
addLine(cube[j].a.y, cube[j].b.y, cube[j].b.x, -1, cnt++);
}
}
sort(line, line + cnt, cmp);
for (int j = 0; j < cnt - 1; ++j)
{
update(my[line[j].y1], my[line[j].y2], line[j].flag, 0, cnty - 1, 1);
ans += (zz[i+1] - zz[i]) * (long long)more[1] * (line[j+1].x - line[j].x);
}
update(my[line[cnt-1].y1], my[line[cnt-1].y2], line[cnt-1].flag, 0, cnty - 1, 1);
}
printf("%I64d\n", ans);
}
int main()
{
scanf("%d", &t);
for (int cas = 1; cas <= t; ++cas)
{
scanf("%d", &n);
for (int i = 0; i < n; ++i)
{
cube[i].a.get();
yy[i*2] = cube[i].a.y;
zz[i*2] = cube[i].a.z;
cube[i].b.get();
yy[i*2+1] = cube[i].b.y;
zz[i*2+1] = cube[i].b.z;
}
printf("Case %d: ", cas);
solve();
}
return 0;
}
C++版本三
#define _CRT_SECURE_NO_WARNINGS
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <string>
#include <map>
#define Mod 1000000
#define ll long long
#define se second
#define fi first
#define pb push_back
#define INF 0x3f3f3f3f
#define de(x) cout << #x << " = "<< x << endl;
#define eps 1e-6
#define db double
#define lson l, mid, t<<1
#define rson mid+1, r, t<<1|1
#define rep(i,a,b) for (int i=(a);i<(b);++i)
#define per(i,a,b) for (int i=(a);i>(b);--i)
#define sz(a) (a).size()
#define vi vector<int >
using namespace std;
int T, n;
ll ans, tot;
ll cnt[10005], sum1[10005], sum2[10005], sum3[10005];
ll all[10005], zz[10005], po;
struct node
{
ll x, y, z, X, Y, Z;
node(ll a,ll b,ll c,ll d,ll e,ll f)
{
x = a; y = b; z = c;
X = d; Y = e; Z = f;
}
node() {};
};
struct seg
{
ll l, r, h, v;
seg(ll a, ll b, ll c, ll d)
{
l = a; r = b; h = c; v = d;
}
seg(){}
};
bool cmp(seg a, seg b){ return a.h < b.h;}
void push_up(ll l, ll r, ll t)
{
if (cnt[t] > 2) sum3[t] = sum2[t] = sum1[t] = all[r + 1] - all[l];
else if (cnt[t] == 2)
{
sum2[t] = sum1[t] = all[r + 1] - all[l];
sum3[t] = sum1[t << 1] + sum1[t << 1 | 1];
}
else if (cnt[t] == 1)
{
sum1[t] = all[r + 1] - all[l];
sum2[t] = sum1[t << 1] + sum1[t << 1 | 1];
sum3[t] = sum2[t << 1] + sum2[t << 1 | 1];
}
else if (l == r)
{
sum1[t] = sum2[t] = sum3[t] = 0;
}
else
{
sum1[t] = sum1[t << 1] + sum1[t << 1 | 1];
sum2[t] = sum2[t << 1] + sum2[t << 1 | 1];
sum3[t] = sum3[t << 1] + sum3[t << 1 | 1];
}
}
void update(ll L, ll R, ll v, ll l, ll r, ll t)
{
if (L <= l && r <= R)
{
cnt[t] += v;
push_up(l, r, t);
return;
}
ll mid = (l + r) >> 1;
if (L <= mid) update(L, R, v, lson);
if (R > mid)update(L, R, v, rson);
push_up(l, r, t);
}
void inti()
{
memset(cnt, 0, sizeof(cnt));
memset(sum1, 0, sizeof(sum1));
memset(sum2, 0, sizeof(sum2));
memset(sum3, 0, sizeof(sum3));
memset(all, 0, sizeof(all));
tot = 0;
po = 0;
}
int main()
{
cin >> T;
for (int o = 1; o <= T; o++)
{
ans = 0;
node a[5005];
memset(zz, 0, sizeof(zz));
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
ll x, y, z, X, Y, Z;
scanf("%I64d%I64d%I64d%I64d%I64d%I64d", &x, &y, &z, &X, &Y, &Z);
a[i] = node(x, y, z, X, Y, Z);
zz[i] = z;
zz[i + n] = Z;
}
sort(zz + 1, zz + 2 * n + 1);
int m = unique(zz + 1, zz + 2 * n + 1) - zz - 1;
for (int i = 1; i < m; i++)
{
inti();
ll number = 0, lp = 0;
seg b[5005];
for (int j = 1; j <= n; j++)
if (a[j].z <= zz[i] && a[j].Z > zz[i])
{
b[++number] = seg(a[j].x, a[j].X, a[j].y, 1);
b[++number] = seg(a[j].x, a[j].X, a[j].Y, -1);
all[++lp] = a[j].x;
all[++lp] = a[j].X;
}
sort(all + 1, all + lp + 1);
ll k = unique(all + 1, all + lp + 1) - all - 1;
sort(b + 1, b + number + 1, cmp);
for (int j = 1; j < number; j++)
{
ll l = lower_bound(all + 1, all + k + 1, b[j].l) - all;
ll r = lower_bound(all + 1, all + k + 1, b[j].r) - all;
if (l < r) update(l, r - 1, b[j].v, 1, k, 1);
tot += sum3[1] * (b[j + 1].h - b[j].h);
// po += sum1[1] * (b[j + 1].h - b[j].h);
}
ans += tot * (zz[i + 1] - zz[i]);
}
printf("Case %d: %I64d\n", o, ans);
}
//system("pause");
return 0;
}
京公网安备 11010502036488号