hdu1542 Atlantis(扫描线+线段树+离散)矩形相交面积
线段 矩形 面积 离散 相交 扫描线
2023-09-14 09:06:21 时间
题目链接:点击打开链接
题目描写叙述:给定一些矩形,求这些矩形的总面积。假设有重叠。仅仅算一次
解题思路:扫描线+线段树+离散(代码从上往下扫描)
代码:
#include<cstdio> #include <algorithm> #define MAXN 110 #define LL ((rt<<1)+1) #define RR ((rt<<1)+2) using namespace std; int n; struct segment{ double l,r,h; int f; bool operator<(const segment& b)const{ return h>b.h; } }sg[2*MAXN]; double pos[2*MAXN]; int id; void addSegment(double x1,double y1,double x2,double y2){ sg[id].l=x1;sg[id].r=x2; sg[id].h=y1;sg[id].f=1; pos[id++]=x1; sg[id].l=x1;sg[id].r=x2; sg[id].h=y2;sg[id].f=-1; pos[id++]=x2; } int binary(double key,int low,int high){ while(low<=high){ int mid=(low+high)/2; if(pos[mid]==key) return mid; else if(key<pos[mid]) high=mid-1; else low=mid+1; } return -1; } struct Tree{ int l,r; int cover; double len; }tree[8*MAXN]; void build(int rt,int l,int r){ tree[rt].l=l; tree[rt].r=r; tree[rt].cover=0; tree[rt].len=0; if(l==r-1) return; int mid=(l+r)>>1; build(LL,l,mid); build(RR,mid,r); } void pushup(int rt){ if(tree[rt].cover) tree[rt].len=pos[tree[rt].r]-pos[tree[rt].l]; else if(tree[rt].l==tree[rt].r-1) tree[rt].len=0; else tree[rt].len=tree[LL].len+tree[RR].len; } void update(int rt,int l,int r,int f){ if(tree[rt].l==l&&tree[rt].r==r){ tree[rt].cover+=f; pushup(rt); return; } int mid=(tree[rt].l+tree[rt].r)>>1; if(r<=mid) update(LL,l,r,f); else if(l>=mid) update(RR,l,r,f); else{ update(LL,l,mid,f); update(RR,mid,r,f); } pushup(rt); } int main(){ int Case=0; while(scanf("%d",&n)!=EOF&&n!=0){ id=0; double x1,y1,x2,y2; for(int i=0;i<n;++i){ scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2); addSegment(x1,y1,x2,y2); } n=(n<<1); sort(sg,sg+n); sort(pos,pos+n); int m=1; for(int i=1;i<n;++i) if(pos[i]!=pos[i-1]) pos[m++]=pos[i]; build(0,0,m-1); double ans=0; int l=binary(sg[0].l,0,m-1); int r=binary(sg[0].r,0,m-1); update(0,l,r,sg[0].f); for(int i=1;i<n;i++){ ans+=(sg[i-1].h-sg[i].h)*tree[0].len; l=binary(sg[i].l,0,m-1); r=binary(sg[i].r,0,m-1); update(0,l,r,sg[i].f); } printf("Test case #%d\n",++Case); printf("Total explored area: %.2f\n\n",ans); } return 0; }
相关文章
- 简单线段树模板[通俗易懂]
- HDU 1556-差分数组和线段树的对比分析-Color the ball
- zkw线段树 学习笔记
- 别人写线段树写得脑壳疼,你却用二次元少女在骗分……
- LeetCode周赛285,再次翻车,时隔6年,没能写出的线段树
- acwing-个简单的整数问题2(线段树+懒惰标记)「建议收藏」
- 蓝桥杯 分苹果(线段树)---------C语言—菜鸟级
- 算法训练 格子操作(线段树)-----------C语言—菜鸟级
- 计算几何之判断线段相交
- 计算几何之线段相交问题(平面扫描)
- 线段树模板
- 【综合笔试题】难度 4/5,字符处理的线段树经典运用
- 线段树笔记
- 图解线段树
- 空间判断点是否在线段上
- 数据结构之线段树
- 第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-8 算法训练 操作格子 线段树
- 线段树QWQ
- 线段树(结构体建法_QAQ)
- 最大数maxnumber (HYSBZ 1012)(线段树区间查询和单点修改)(优雅的暴力)
- Allegro使用Skill语言实现根据两点p1,p2确定的线段判断是否与bbox构成的矩形相交的函数
- 线段树模板与练习
- 【OpenGL】十二、OpenGL 绘制线段 ( 绘制单条线段 | 绘制多条线段 | 依次连接的点组成的线 | 绘制圈 | 绘制彩色的线 )
- 【Android UI】绘制圆角矩形进度条 ① ( 像素值转化 dp -> px | Paint 标志位设置 | Paint 画笔线帽样式设置 | Paint 画笔线段连接处样式设置 )