题意:求三个矩形体积的并

链接:点我

枚举z

 #include<stdio.h>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
#include<vector>
#include<math.h>
#include<map>
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
#define maxn 1100
#define mem(a,b) (memset(a),b,sizeof(a))
#define lmin 1
#define rmax len
#define lson l,(l+r)/2,rt<<1
#define rson (l+r)/2+1,r,rt<<1|1
#define root lmin,rmax,1
#define now l,r,rt
#define int_now int l,int r,int rt
#define INF 99999999
#define LL long long
#define mod 10007
#define eps 1e-6
#define zero(x) (fabs(x)<eps?0:x)
#define LL __int64
map<int,int>mp;
int du[maxn*];
struct lines
{
int x;
int y,yy;
int z,zz;
int leap;
friend bool operator <(const lines &a,const lines &b)
{
return a.x<b.x;
}
} line[maxn*];
int num[maxn**];
int sum[maxn**];
int kum[maxn**];
int cover[maxn**];
void push_down(int_now)
{ }
void push_up(int_now)
{
int len=du[r+]-du[l];
if(cover[rt]==)
{
num[rt]=num[rt<<]+num[rt<<|];
sum[rt]=sum[rt<<]+sum[rt<<|];
kum[rt]=kum[rt<<]+kum[rt<<|];
}
if(cover[rt]==)
{
num[rt]=len;
sum[rt]=num[rt<<]+num[rt<<|];
kum[rt]=sum[rt<<]+sum[rt<<|];
}
if(cover[rt]==)
{
num[rt]=len;
sum[rt]=len;
kum[rt]=num[rt<<]+num[rt<<|];
}
if(cover[rt]>=)
{
num[rt]=len;
sum[rt]=len;
kum[rt]=len;
}
}
void creat()
{
memset(cover,,sizeof(cover));
memset(num,,sizeof(num));
memset(sum,,sizeof(sum));
memset(kum,,sizeof(kum));
}
void updata(int ll,int rr,int x,int_now)
{
if(ll>r||rr<l)return;
if(ll<=l&&rr>=r)
{
cover[rt]+=x;
push_up(now);
return;
}
updata(ll,rr,x,lson);
updata(ll,rr,x,rson);
push_up(now);
}
int main()
{
int T,cas;
scanf("%d",&T);
cas=;
while(T--)
{
cas++;
int n,x,y,z,xx,yy,zz;
mp.clear();
scanf("%d",&n);
LL ls=;
du[]=-;
for(int i=; i<=n; i++)
{
scanf("%d%d%d%d%d%d",&x,&y,&z,&xx,&yy,&zz);
line[i*-].x=x;
line[i*-].y=y;
line[i*-].yy=yy;
line[i*-].z=z;
line[i*-].zz=zz;
line[i*-].leap=;
line[i*].x=xx;
line[i*].y=y;
line[i*].yy=yy;
line[i*].z=z;
line[i*].zz=zz;
line[i*].leap=-;
du[ls++]=y;
du[ls++]=yy;
}
sort(line+,line+n*+);
sort(du+,du+ls);
int len=;
for(int i=; i<ls; i++)
{
if(du[i]!=du[i-])
{
mp[du[i]]=len;
du[len++]=du[i];
}
}
len-=;
LL are=;
int st=;
creat();
for(int j=-; j<; j++)
{
st=;
for(int i=; i<=n*; i++)
{
int l,r;
l=mp[line[i].y];
r=mp[line[i].yy];
if(line[i].z>j||line[i].zz<=j)continue;
LL x,y;
x=(LL)kum[];
y=(LL)line[i].x-st;
are+=x*y;
updata(l,r-,line[i].leap,root);
st=line[i].x;
}
}
printf("Case %d: %I64d\n",cas,are);
}
return ;
}

最新文章

  1. 驱动01.LED
  2. ACM Arithmetic Expression
  3. ELK日志管理之——elasticsearch部署
  4. 六个创建模式之抽象工厂模式(Abstract Factory Pattern)
  5. as3 中 textfiled的htmltext 的常用属性
  6. [051] 微信公众平台开发教程第22篇-怎样保证access_token长期有效
  7. C# Socket基础(一)之启动异步服务监听
  8. android 自定义ratingbar 图片显示不全的解决方案
  9. BNU Questions and answers
  10. 201521123088《java程序设计》第十周学习总结
  11. MongoDB的安装与配置
  12. hdu_1028_母函数
  13. DDoS的类型及原理
  14. MySQL(一)MySQL基础介绍
  15. mxnet 查看 Sym shape
  16. PAT 1086 就不告诉你(15 )(代码)
  17. 团队作业Week6:规格说明书编写
  18. 使用Eclipse Memory Analyzer分析Tomcat内存溢出
  19. NBUT 1220 SPY 2010辽宁省赛
  20. PythonWEB框架之Flask--2

热门文章

  1. h5+js随机拖动鼠标产生动画效果
  2. JFinal向客户端渲染图片的方法
  3. bootstrap入门项目备份
  4. Sqlmap与burpsuite动态更新某些参数
  5. java线上应用故障排查之二:高内存占用【转】
  6. 136.Single Number---异或、位运算
  7. acm专题--并查集
  8. 1.第一个hello word
  9. LightOJ 1323 Billiard Balls(找规律(蚂蚁爬木棍))
  10. python之pandas&amp;&amp;DataFrame(二)