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

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

• Linux • 阅读 114

还是老规矩，传送门 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语言 刷题答案下载！

大家都在看

  • Docker部署Dotnet

    方法一：打包+镜像 部署 将要部署的项目及其依赖的项目上传至指定文件夹下 要部署的项目添加Docker支持，生成Dockerfile文件 将生成的Dockerfile文件上传至要部…

    Linux 2023年6月13日
    0116

  • 一文搞懂 Redis 架构演化之路

    作者：ryetan，腾讯 CSIG 后台开发工程师 现如今 Redis 变得越来越流行，几乎在很多项目中都要被用到，不知道你在使用 Redis 时，有没有思考过，Redis 到底是…

    Linux 2023年5月28日
    0106

  • 01-MySQL连接查询、聚合函数

    1、连接查询 1.1、左连接 以左表为基准进行查询，左表数据回全部显示出来 右表中如果匹配连接条件的数据则显示相应字段的数据，如果不匹配，则显示为NULL 1.2、右连接 以右表为…

    Linux 2023年6月7日
    0129

  • centos快速搭建nfs共享

    一、nfs服务器端 01.安装nfs服务 yum -y install nfs-utils 02.创建存储目录 mkdir -p /data/2haohr_backup 03.设置…

    Linux 2023年6月6日
    0113

  • 最好的Java开发工具—IDEA

    IDEA的使用 IntelliJ IDEA工具的使用 1. 常见的Java集成开发工具 Eclipse IBM团队研发的一个开源的非常好用的集成开发环境。寓意：吞并Sun公司。不过…

    Linux 2023年6月14日
    0109

  • 面试题：海量数据处理利器-布隆过滤器

    概念 原理 布隆过滤器的使用场景 简单模拟布隆过滤器 Guava布隆过滤器 Redis布隆过滤器 布谷鸟过滤器 作者：小牛呼噜噜 | https://xiaoniuhululu.c…

    Linux 2023年6月6日
    0174

  • 通过过滤器实现前后端分离的跨域问题

    跨域指的是浏览器不能执行其他网站的脚本。它是由浏览器的同源策略造成的，是浏览器对JavaScript施加的安全限制。在做前后端分离项目的时候就需要解决此问题。 创建过滤器解决跨域问…

    Linux 2023年6月7日
    0105

  • GO redis

    csharp;gutter:true; package main</p> <p>import ( "fmt" "github….

    Linux 2023年5月28日
    0102

  • Nginx禁止ip加端口访问

    使用 iptables 限制对应端口，再利用Nginx将80端口转发到对应端口 CentOS7默认的防火墙是 firewalle，先看看服务器中有没有安装 iptables [ro…

    Linux 2023年6月14日
    093

  • 【证券从业】金融基础知识-第五章 债券02

    注1：后续学习并整理到第八章，全书完结后再合并成一个笔记进行源文件分享 注2：本章内容巨多，大约分为两篇文章记录消化 posted @2022-06-09 23:55 陈景中 阅读…

    Linux 2023年6月13日
    093

  • String为什么不是基本数据类型

    java虚拟机处理基础类型与引用类型的方式是不一样的，对于基本类型，java虚拟机会为其分配数据类型实际占用的内存空间，对于引用类型变量，他仅仅是一个指向堆区中某个实例的指针。 O…

    Linux 2023年6月7日
    0108

  • 19-TCP、UDP的区别和应用场景

    可靠性TCP 提供交付保证，这意味着一个使用TCP协议发送的消息是保证交付给客户端的，如果消息在传输过程中丢失，那么它将重发。UDP是不可靠的，它不提供任何交付的保证，一个数据包在…

    Linux 2023年6月7日
    085

  • 每天一个 HTTP 状态码 201

    201 Created 表示请求成功，在服务器端创建了一个新资源… 201 Created 201 Created 表示客户端的请求已经成功完成，结果是创建了一个新资源…

    Linux 2023年6月7日
    0131

  • js打印前几天或后几天的日期

    创作对你我有价值的，喜欢交朋友，失忆王子，期待与你共同探讨，技术qq群153039807 Original: https://www.cnblogs.com/hshanghai/p…

    Linux 2023年6月13日
    0106

  • Java基础学习笔记

    Java 入门基础编程笔记 Java 入门基础编程视频课件地址：点击我啦哟 提取码：50ME 1 前言 1.1 软件开发介绍 软件，即一系列按照特定顺序组织的计算机数据和指令的集合…

    Linux 2023年6月13日
    0112

  • conda 和 pip 的具体区别

    pip install 安装包时不会自动安装所需的其他依赖包，只是在缺少其他依赖包时作错误提示，这时需要手动安装其他依赖包 pip 不会将python看成包，不能对环境中的pyth…

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