hdu 1542 Atlantis (线段树+扫描线求矩形面积并,模板题)

hdu1542题目链接

题意:

求n(100)个矩形的面积并。

思路:

扫描线+线段树

题目是2000年中欧区域赛的题目,虽然年代久远,但是有好几个点还是很值得学习的。

 

首先是离散化的适用范围:

之前比较常用的是将比较大的整数值离散化,常常是因为数值太大无法作为下标。

那么其实,浮点数有的时候也需要进行离散化,比如作为数组的下标,比如用来枚举。

做法上是和将较大的整数值离散化没有区别,因为遇到的题目不多,所以特意记录一下。

 

第二点是扫描线的思想:

其实扫描线的思想很早就接触过,noip2011的时候,tyvj上有一道类似的题目,不过是一唯的,当时印象深刻的是@Ocean 兄的那个比喻:

一段公路上右很多区间要收不同的费用,区间的开始给一个标记,表示该段区间对答案有贡献,区间的结束拿走该标记,表示该段区间对答案的贡献结束。

这就是扫描线的思想。

 

第三个是处理线段覆盖问题的一般做法:

通常线段树的节点处理的都是点,处理线段的时候就会比较麻烦。

  另外很重要的一点就是, 线段树都是维护一个点集, 但是对于边的问题就会变得很麻烦,  我们可以按照区间左端点建立线段树, 那么一个点表示的就不是点了, 而是起点在这个点的一个线段。  这样的话, 右区间就要相应的-1, 例如更新区间[1, 4], 就相当于更新标号为[1, 3]的线段。

这也是处理线段覆盖问题的通用方法。

对于上面引用中提到的例子中“更新[1,4],就相当于更新标号为[1,3]的线段”,是因为标号为1的节点代表区间[1,2],标号为2的节点代表区间[2,3],标号为3的节点代表期间[3,4]

 

接下来具体讨论这道题目的做法:

将矩形按平行x轴方形构建扫描线(只是思想,不用实际构造),

每个矩形2条平行x轴的边分类{上边,下边}2类,如果我们从下往上“扫描”线,那么[下边]就表示了对答案贡献的开始,[下边]就表示了对答案贡献的结束。

  • 扫描线扫描的过程(建议配合代码模拟)

    以下图转载自@kk303的博客

初始状态

初始状态

这里写图片描述

扫到最下边的线, 点13更新为1

这里写图片描述

扫到第二根线, 此时S=lcnt!=0h线, 得到绿色的面积, 加到答案中去, 随后更新计数

这里写图片描述

同上, 将黄色的面积加到答案中去

这里写图片描述

同上, 将灰色的面积加到答案中去

这里写图片描述

同上, 将紫色的面积加到答案中去

这里写图片描述

 

 

 

参考资料:

HDU 1542 Atlantis(线段树:扫描线)

HDU 1542 Atlantis(线段树求矩形面积并)

矩形面积并、矩形面积交、矩形周长并(线段树、扫描线总结)

 

 

 

作者: CrazyKK

ex-ACMer@hust,stackoverflow-engineer@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz