hdu3255扫描线：带权面积交转体积交

2023-10-24 00:00:21

手贱把i打成j，调了半天

/*
面积并转体积并，长方体高度为作物价格
算体积并：在笛卡尔坐标系的y轴上建立线段树cnt记录区间被完全覆盖的次数，sum记录区间被覆盖的总长度以平行于xoy的平面从下往上扫描，把穿过扫描面的长方体的上下边加入集合segs,对集合segs里的边排序，然后一根扫描线从下往上扫描
另外，更新是不影响线段边界的 
*/
#include
#include
#include
#include
#include
#define ll long long 
#define maxn 30000*2+10
#define lson l,m,rt<<1
#define rson m,r,rt<<1|1
using namespace std;
struct Seg{int l,r,h,c;Seg(){}Seg(int a,int b,int c,int d):l(a),r(b),h(c),c(d){}bool operator<(const Seg & a)const{return h<a.h;}
}segs[maxn];
struct cube{int x1,y1,z1,x2,y2,z2;cube(){}cube(int a,int b,int c,int d,int e,int f):x1(a),y1(b),z1(c),x2(d),y2(e),z2(f){}
}cubes[maxn];
int seeds[4],n,m;
int y[maxn<<2],toty,tot;
int z[maxn],totz;
map<int,int>mp;
ll cnt[maxn<<2],len[maxn<<2];
void init(){tot=toty=totz=0;mp.clear();memset(cnt,0,sizeof cnt);memset(len,0,sizeof len);
}inline void pushup(int rt,int l,int r){if(cnt[rt]){len[rt]=y[r]-y[l];    }else if(l+1==r) len[rt]=0;else len[rt]=len[rt<<1]+len[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;pushup(rt,l,r);return;}int m=l+r>>1;if(L<m) update(L,R,c,lson);if(R>m) update(L,R,c,rson);pushup(rt,l,r);
}
int main(){int T,a,b,c,d,e;cin >> T;for(int tt=1;tt<=T;tt++){init();cin >> n >> m;for(int i=1;i<=m;i++)scanf("%d",&seeds[i]);z[tot++]=0;//把地平线加上！for(int i=1;i<=n;i++){scanf("%d%d%d%d%d",&a,&b,&c,&d,&e);cubes[i]=cube(a,b,0,c,d,seeds[e]);z[totz++]=seeds[e];y[toty++]=b;y[toty++]=d;}z[totz++]=0;sort(z,z+totz);totz=unique(z,z+totz)-z;//离散化z轴sort(y,y+toty);toty=unique(y,y+toty)-y;//离散化x轴for(int i=0;ii;ll res=0;for(int i=0;i1;i++){tot=0;//初始化memset(segs,0,sizeof segs);/* memset(cnt,0,sizeof cnt);memset(len,0,sizeof len); */for(int j=1;j<=n;j++){//遍历所有cubes，把符合条件的加进去if(cubes[j].z1<=z[i] && cubes[j].z2>=z[i+1]){segs[tot++]=Seg(cubes[j].y1,cubes[j].y2,cubes[j].x1,1);segs[tot++]=Seg(cubes[j].y1,cubes[j].y2,cubes[j].x2,-1);}}sort(segs,segs+tot);for(int j=0;j){if(j!=0)res+=(ll)(z[i+1]-z[i])*(segs[j].h-segs[j-1].h)*len[1];update(mp[segs[j].l],mp[segs[j].r],segs[j].c,0,toty-1,1);}}printf("Case %d: %lld\n",tt,res);}return 0;
}

转载于:https://www.cnblogs.com/zsben991126/p/9960754.html

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！

标签：技术

上一篇 > JAVA 实习五
下一篇 > Python基本数据类型；Part2

Duilib中list控件支持ctrl和shif多行选中的实现

[ICML2015]Batch Normalization:Accelerating Deep Network Training by Reducing Internal Covariate Shif

win10系统微软输入法于eclipse ctrl+shif+f冲突间接处理办法

Codeforces Round #259 (Div. 2) B. Little Pony and Sort by Shif

读LDD3，内存映射与DMA--PAGE_SHIF…

VMware虚拟机安装XP【要先分区，再设置BOOT 启动CD，shif+上移】

更换iBus五笔的左与右Shif

sublime ctrl+shif+f 没用解决办法

idea 对 ctrl + z 的撤销是 ctrl + shif + z

计算机最早的设计师应用于,计算机应用基础选择题doc.doc

win10自带截图神器：Win+Shift+S

Python基础之文件目录操作

python简述目录_Python基础之文件目录操作(示例代码)

tp5 如何做数据采集

任务2-7(服务器字体+阿里巴巴矢量库)

html标签（1)：h1~h6,p,br,pre,hr

TI 电量计介绍与芯片选型指南

几款TI电源芯片简介

TI DSP芯片C2000系列读取FLASH数据

德州仪器(Ti)平台嵌入式开发基础

TI三相电机智能栅极驱动芯片特点分类

省选模拟（12.08） T3 圈圈圈圈圈圈圈圈

Hadoop生态圈技术栈（上）

大数据开发基础入门与项目实战（三）Hadoop核心及生态圈技术栈之6.Impala交互式查询

小猿圈之Linux下Mysql 操作命令

大数据Hadoop生态圈常用面试题

大数据开发基础入门与项目实战（三）Hadoop核心及生态圈技术栈之4.Hive DDL、DQL和数据操作

备战Noip2018模拟赛11（B组）T3 Monogatari 物语

【智能优化算法-圆圈搜索算法】基于圆圈搜索算法Circle Search Algorithm求解单目标优化问题附matlab代码

NYOJ 78 圈水池

递归问题跑道汽车绕圈问题 Python实现

Hadoop生态圈（三）：MapReduce

hdu3255扫描线：带权面积交转体积交

相关文章