hdu 1828 Picture (线段树+扫描线 求 矩形周长并)

题目链接

题意:

求矩形周长并。

思路:

线段树+扫描线。

和前面的求面积并比较类似,我们先考虑平行x轴的线段,考虑线段树,维护的一段区间中被矩形覆盖的次数cnt和至少覆盖一次的长度的len.

只不过我们这次求的是每条扫描线的长度对周长的贡献,因此不需要乘高度。

 

需要注意的是,每条扫描线对周长的贡献,是目前扫描线的长度,与上一次扫描线长度的差的绝对值。(不是与上一次答案的差的绝对值!)

演示x轴求长度和的部分  图片来自 lwt聚聚的博客
这里写图片描述

以及一个小细节是,求面积的时候,最后一条扫描线对答案是没有贡献的(因为每次是求当前扫描线与下一条扫描线之间的面积)

但是求周长的时候,最后一条扫描线是一定会对答案有贡献的。

 

作者: CrazyKK

ex-ACMer@hust,stackoverflow-engineer@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz