题意:

。。。就是求体积交。。。

解析:

  把每一层z抽出来,计算面积交, 然后加起来即可。。!

去看一下 二维面积交的代码 再看看这个三维面积交的代码。。 down函数里 你发现了什么规律!!!

参考二维面积交:https://www.cnblogs.com/WTSRUVF/p/9274318.html

代码如下

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#define mem(a, b) memset(a, b, sizeof(a))
using namespace std;
const int maxn = , INF = 0x7fffffff;
typedef long long LL;
int X[maxn]; struct node{
int l, r, w;
int lx, rx, sum, lsum, llsum;
}Node[maxn]; struct edge{
int lxx, rxx, y, z1, z2;
int f;
}Edge[maxn*]; int cmp(edge a, edge b)
{
return a.y < b.y;
} void build(int k, int ll, int rr)
{
Node[k].l = ll, Node[k].r = rr;
Node[k].w = Node[k].sum = Node[k].lsum = Node[k].llsum = ;
Node[k].lx = X[ll];
Node[k].rx = X[rr];
if(ll + == rr) return;
int m = (ll + rr) / ;
build(k*, ll, m);
build(k*+, m, rr);
} void down(int k)
{
int len = Node[k].rx - Node[k].lx;
if(Node[k].w >= )
{
Node[k].sum = Node[k].lsum = Node[k].llsum = len;
}
else if(Node[k].w == )
{
Node[k].lsum = Node[k].llsum = len;
if(Node[k].l + == Node[k].r)
Node[k].sum = ;
else
Node[k].sum = Node[k*].lsum + Node[k*+].lsum;
}
else if(Node[k].w == )
{
Node[k].lsum = len;
if(Node[k].l + == Node[k].r)
Node[k].llsum = Node[k].sum = ;
else
{
Node[k].llsum = Node[k*].lsum + Node[k*+].lsum;
Node[k].sum = Node[k*].llsum + Node[k*+].llsum;
}
}
else
{
if(Node[k].l + == Node[k].r)
Node[k].sum = Node[k].lsum = Node[k].llsum = ;
else
{
Node[k].lsum = Node[k*].lsum + Node[k*+].lsum;
Node[k].llsum = Node[k*].llsum + Node[k*+].llsum;
Node[k].sum = Node[k*].sum + Node[k*+].sum;
}
} } void update(int k, edge e)
{
if(Node[k].lx == e.lxx && Node[k].rx == e.rxx)
{
Node[k].w += e.f;
down(k);
return;
}
if(e.rxx <= Node[k*].rx) update(k*, e);
else if(e.lxx >= Node[k*+].lx) update(k*+, e);
else
{
edge temp = e;
temp.rxx = Node[k*].rx;
update(k*, temp);
temp = e;
temp.lxx = Node[k*+].lx;
update(k*+, temp);
}
down(k);
} int main()
{
int T, kase = ;
scanf("%d",&T);
while(T--)
{
int n, cnt = ;
scanf("%d",&n);
for(int i=; i<n; i++)
{
int x1, y1, z1, x2, y2, z2;
scanf("%d%d%d%d%d%d", &x1, &y1, &z1, &x2, &y2, &z2);
Edge[++cnt].lxx = x1, Edge[cnt].rxx = x2, Edge[cnt].y = y1, Edge[cnt].f = , Edge[cnt].z1= z1, Edge[cnt].z2 = z2;
X[cnt] = x1;
Edge[++cnt].lxx = x1, Edge[cnt].rxx = x2, Edge[cnt].y = y2, Edge[cnt].f = -, Edge[cnt].z1= z1, Edge[cnt].z2 = z2;
X[cnt] = x2;
}
sort(Edge+, Edge+cnt+, cmp);
sort(X+, X+cnt+);
int m = unique(X+, X+cnt+) - (X+);
LL ret = ;
for(int i=-; i<=; i++)
{
build(, , m);
int ans = ;
edge line[maxn];
for(int j=; j<=cnt; j++)
{
if(Edge[j].z1 <= i && Edge[j].z2 > i)
line[++ans] = Edge[j];
}
for(int j=; j<ans; j++)
{
update(, line[j]);
ret += (LL)Node[].sum * (line[j+].y - line[j].y);
}
}
printf("Case %d: %lld\n",++kase,ret); } return ;
}

最新文章

  1. API Monitor v2.0 Alpha-r13 (32+64) 汉化版
  2. opengl
  3. VisualRust + VisualGDB编辑调试Rust
  4. Swift基础语法(三)
  5. Divide and conquer:Garland(POJ 1759)
  6. 关于call 和 apply
  7. FROM_UNIXTIME()和UNIX_TIMESTAMP()函数的区别
  8. search in rotated sorted array leetcode
  9. C# Json帮助类
  10. HDU3466背包01
  11. virtualenv -- python虚拟沙盒
  12. Javascript null和undefined
  13. 新图形API为unity5 带来了什么&amp;下一代新图形API的好处
  14. Linux中命令行编译java接口总是提示找不到符号的疑难杂症的解决
  15. CountDownLatch和CyclicBarrier的区别(转)
  16. 用一个jsp实现对数据库发访问
  17. requests爬取网页的通用框架
  18. BZOJ 1982: [Spoj 2021]Moving Pebbles [博弈论 对称]
  19. 第一次Scrum冲刺——Life in CCSU
  20. Java的动手动脑(五)

热门文章

  1. curl发送json格式数据
  2. jQuery与js例子
  3. Log4j使用笔记
  4. SpringMVC之声明式校验
  5. 两个非常好的bootstrap模板,外送大话设计模式!
  6. [Oracle][OnlineREDO]数据库无法启动时的对应策略:
  7. [Oracle]如何取Control File 的Dump
  8. ETL流程介绍及常用实现方法
  9. 限流——spring-cloud-zuul-ratelimit
  10. CentOS上yum方式安装配置LNMP