1. Johngo学长首页
  2. 技术点详细复盘专题
  3. Linux

线段树扫描线（一） 矩形面积 以hdu 1542为例

• Linux • 阅读 98

还是老规矩，传送门 hdu 1542

不做过多解释了，就是给出n个矩形，求出这些矩形所覆盖的面积和。由于n很小，因而这道题不是必须用线段树

先想想怎么办，先来一个例图（稍微有点复杂）

线段树扫描线（一） 矩形面积 以hdu 1542为例

根据数学知识，我们可以像这样：

线段树扫描线（一） 矩形面积 以hdu 1542为例

将它用红线分割，然后维护每条红线被矩形覆盖的部分的长度，然后乘以两条红线之间的距离，最后累加每一部分的面积而得到答案，没什么问题吧。

接下来，问题转化为维护线段的长度了，于是我们考虑线段树，但我们发现了一个重大问题：x坐标是实数，不能直接用线段树维护，但我们不虚，把浮点离散成整数不就好了吗。

然后，重中之重来了，线段树里存什么：

（1）：存节点是否被覆盖：用脑子思考一下，就会发现这不对：例如，离散后最大坐标为6，插入一条线段[2,6]，那么3,4之间的一段就消失了，必然WA，就算用强大的码力解决了这个问题，代码也必然会十分恶心，因此，我们不要这样存储

（2）：存一段线是否被覆盖：这是正确的，但鉴于鄙人语文不太好，难以用语言解释，上一张图：

例如，离散后最大坐标为6，则我们要这样：

线段树扫描线（一） 矩形面积 以hdu 1542为例

然而，我为了代码好写，传参数时传的依然是离散后的点坐标，因此，dis(L,R)=val[R+1]-val[L]，

接下来，就是对线段树进行改造，使之能正确维护线段长度

我们可以这样考虑，在矩形下侧的边进入时，加一，而在上侧的边进入时，加负一，然后，对线段树进行修改，每一个节点中记录这个区间被完全覆盖的次数和被覆盖的长度，

求解前，对2n条边按高度排序，从最低的边开始，逐个枚举到最高的一条边，累加答案即可。

大体的思路有了，但我还要多说两句：

1.输出时两组之间有空行，每组的两行之间没有空行，正确的输出语句应该像下面这样

printf("Test case #%d\nTotal explored area: %.2lf\n\n",cas,ans);

其中：cas记录这是第几组数据，ans为这组数据的结果

2.这道题不建议大家使用万能头文件，因为y1在cmath中是一个函数，这样做会导致CE，当然，强烈不建议手欠打上

#include

习惯不用y1的神犇们请忽略此条建议。

好了，奉上代码

  1 #include
  2 #include
  3 #include
  4 #include
  5 using namespace std;
  6 map<double,int> mp;
  7 double ls[5000],x1,x2,_y1,y2;
  8 int n,cnt,cd;
  9 struct edge
 10 {
 11     int l,r,val;
 12     double ll,rr,h;
 13 }eds[2500];
 14 struct node
 15 {
 16     int cov;
 17     double dis;
 18 }tre[2500];
 19 int cmp(edge a,edge b){return a.h<b.h;}
 20 void init()
 21 {
 22     cnt=1;
 23     cd=1;
 24     mp.clear();
 25     memset(ls,0,sizeof(ls));
 26     //由于每次树都会被正好加成0，不用对树进行重置 
 27 }
 28 int fd(double tar)
 29 {
 30     int l=1,r=cd;
 31     while(l<r)
 32     {
 33         int mid=(l+r)/2;
 34         if(ls[mid]<tar)
 35         {
 36             l=mid+1;
 37         }
 38         else
 39         {
 40             r=mid;
 41         }
 42     }
 43     return l;
 44 }
 45 void pushup(int L,int R,int nc)
 46 {
 47     if(tre[nc].cov)
 48     {
 49         tre[nc].dis=ls[R+1]-ls[L];
 50     }
 51     else
 52     {
 53         if(L==R)
 54         {
 55             tre[nc].dis=0;
 56         }
 57         else
 58         {
 59             tre[nc].dis=tre[2*nc].dis+tre[2*nc+1].dis;
 60         }
 61     }
 62 }
 63 void ins(int l,int r,int dt,int nc,int L,int R)
 64 {
 65     if(l=R)
 66     {
 67         tre[nc].cov+=dt;
 68         if(tre[nc].cov)
 69         {
 70             tre[nc].dis=ls[R+1]-ls[L];
 71         }
 72         else
 73         {
 74             if(L==R)
 75             {
 76                 tre[nc].dis=0;
 77             }
 78             else
 79             {
 80                 tre[nc].dis=tre[2*nc].dis+tre[2*nc+1].dis;
 81             }
 82         }
 83         return;
 84     }
 85     int mid=(L+R)/2;
 86     if(lmid)
 87     {
 88         ins(l,r,dt,2*nc,L,mid);
 89     }
 90     if(r>mid)
 91     {
 92         ins(l,r,dt,2*nc+1,mid+1,R);
 93     }
 94     pushup(L,R,nc);
 95 }
 96 int main()
 97 {
 98     int cas=1;
 99     while(1)
100     {
101         scanf("%d",&n);
102         if(n==0)
103         {
104             return 0;
105         }
106         init();
107         for(int i=1;i)
108         {
109             scanf("%lf%lf%lf%lf",&x1,&_y1,&x2,&y2);
110             eds[cnt].h=_y1;
111             eds[cnt].ll=x1;
112             eds[cnt].rr=x2;
113             eds[cnt].val=1;
114             cnt++;
115             eds[cnt].h=y2;
116             eds[cnt].ll=x1;
117             eds[cnt].rr=x2;
118             eds[cnt].val=-1;
119             cnt++;
120             if(!mp[x1])
121             {
122                 mp[x1]=1;
123                 ls[cd]=x1;
124                 cd++;
125             }
126             if(!mp[x2])
127             {
128                 mp[x2]=1;
129                 ls[cd]=x2;
130                 cd++;
131             }
132         }
133         sort(ls+1,ls+cd);
134         for(int i=1;i)
135         {
136             eds[i].l=fd(eds[i].ll);
137             eds[i].r=fd(eds[i].rr);
138         }//从读入到这里都是离散化 
139         sort(eds+1,eds+cnt,cmp);
140         double last=eds[1].h,ans=0;
141         ins(eds[1].l,eds[1].r-1,eds[1].val,1,1,cd-1);
142         for(int i=2;i)
143         {
144             ans+=(eds[i].h-last)*tre[1].dis;
145             ins(eds[i].l,eds[i].r-1,eds[i].val,1,1,cd-1);
146             last=eds[i].h;
147         }
148         printf("Test case #%d\nTotal explored area: %.2lf\n\n",cas,ans);
149         cas++;
150     }
151 };i++;i++

Original: https://www.cnblogs.com/Grharris/p/10389158.html
Author: Grharris
Title: 线段树扫描线（一） 矩形面积 以hdu 1542为例

原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/578006/

转载文章受原作者版权保护。转载请注明原作者出处！

赞 (0)
0

【自取】最近整理的，有需要可以领取学习：



Linux核心资料大放送~

全栈面试题汇总（持续更新&可下载）

一个提高学习100%效率的工具！

【超详细】深度学习面试题目！

LeetCode Python刷题答案下载！

LeetCode Java版刷题答案下载！

LeetCode C++ 版本，抓紧保存！

LeetCode GO语言 刷题答案下载！

大家都在看

  • [云原生]Kubernetes-集群搭建（第2章）

    一、前置知识点 二、kubeadm部署方式介绍 三、安装要求 四、最终目标 五、准备环境 六、环境初始化 6.1 设置系统主机名以及Hosts文件的相互解析 6.2 安装依赖文件（…

    Linux 2023年6月13日
    062

  • Linux 中 图片的产生与查看

    使用场景 当在 Linux 的控制台想要显示一张图片，使用matplotlib.plt.plot() 和matplotlib.plt.show() 会报错。此时可以曲线救国，不直接…

    Linux 2023年6月7日
    067

  • Windows批处理一键添加hosts文件

    批处理一键添加hosts文件 此脚本主要用于安装一些学习软件时需屏弊一些网站，双击一键修改。 @echo off echo 获取Administrator权限 cacls.exe …

    Linux 2023年6月8日
    087

  • JAVA环境变量配置

    java环境配置 下载jdk地址如下： http://www.oracle.com/technetwork/java/javase/downloads/index.html 下载安…

    Linux 2023年6月7日
    0106

  • 投票活动进行中！探讨问题：从互联网大量收集学习资料再包装成产品售卖盈利是否属于侵权违法？

    写在开篇 今天不聊某项技能的知识点，我们聊点别的。那么，到底聊啥好呢？笔者想想… 有了，这两天笔者从一个微信公众号中发现一个非常恶劣的营销行为。事情大概背景是这样的：运…

    Linux 2023年6月7日
    071

  • 《卡死你3000》批量文件复制命令详解

    卡死你3000简介： 名词解释： 批量顺序复制文件：从主控机，到从被控机1，被控机2，复制文件。有卡住问题。 批量并发复制文件：从主控机，到从被控机1，被控机2，复制文件。使用多线…

    Linux 2023年6月13日
    0109

  • Sharding-jdbc 5.1.2案例

    简介 sharding-jdbc案例，版本5.1.2 springboot + mybatis-plus + sharding-jdbc 项目地址：sharding-jdbc-ex…

    Linux 2023年6月7日
    0100

  • haproxy

    haproxy 一.haproxy简介 二.负载均衡 三.haproxy安装 1.yum安装 2.源码安装 2.1 配置文件解析 2.2时间格式 2.3 全局global 2.4 …

    Linux 2023年6月7日
    0102

  • 记一次PowerShell配合Metersploit的艰难提权

    0x01 环境准备 kali（模拟公网攻击机） Windows2008（靶机，装有360、火绒、安全狗、D盾） Powersploit（PowerShell攻击框架） https:…

    Linux 2023年5月28日
    073

  • Emacs 基础offset值

    cc-mode有如下规定：One of the symbols +, -, ++, –, *, or /These special symbols describe a…

    Linux 2023年6月13日
    080

  • Linux——配置主从数据库服务

    主从数据库 Linux中，数据库服务有三种：互为主主，互为主从，一主一从（主从数据库） 服务名 mariadb 协议名 mysql 进程名称 mysqld 端口号 3306 一、改…

    Linux 2023年5月27日
    0103

  • SSH加密原理

    1、SSH初次交换公钥 客户端发起链接请求 服务端返回自己的公钥，以及一个会话ID（这一步客户端得到服务端公钥） 客户端生成密钥对 客户端用自己的公钥异或会话ID，计算出一个值Re…

    Linux 2023年6月7日
    084

  • 常见网络安全设备

    一、防火墙定位：访问控制类产品，网络出现后的第一类安全产品。功能：隔离内网、外网以及DMZ区（业务系统对外发布区，Web应用服务器，邮件服务器等）并控制用户访问。部署方式：通常部署…

    Linux 2023年6月14日
    083

  • 版本控制gitlab

    版本控制gitlab 版本控制gitlab 什么是版本控制gitlab gitlab部署 什么是版本控制gitlab GitLab 是一个用于仓库管理系统的开源项目，使用Git作为…

    Linux 2023年6月6日
    099

  • js中div显示和隐藏钮为什么页面总是跳一下到最上面

    中心动态 产权动态 财经聚焦 点击onclick事件 是因为的href属性，使用了#的缘故，你点击a的时候回到页面的开始，然后才在做click函数，你可以不使用href属性。但是这…

    Linux 2023年6月13日
    096

  • 课间游戏志：斗荧光笔与扒撸咔嚓

    课间游戏志：斗荧光笔与扒撸咔嚓 写这篇博客，主要是想记录两个课间游戏，一个是我于小学四年级时发明的斗荧光笔，一个是初中时班上几个变态发明的扒撸咔嚓，自从这两个游戏被发明以后，我们班…

    Linux 2023年6月6日
    090
亲爱的 Coder【最近整理，可免费获取】👉 最新必读书单  | 👏 面试题下载  | 🌎 免费的AI知识星球