还是老规矩,传送门 hdu 1828
依然不做过多解释,给出n个矩形,求这些矩形组合而成的图形的周长(中间镂空的部分也算)
还是像扫面线(一)一样,自下而上扫描,
我们先只考虑横线,发现只要每次加上被覆盖的区间长度的变化值的绝对值就能统计出横向的答案,
但竖线怎么办?
有一种朴素的办法,自下而上扫过一次后,从左到右在扫一遍,常数问题(好像不卡)
接下来,讲一种更好的办法。
我所说的办法,就是在自下而上扫描时,同时统计出竖线的长度和。
每条竖线的长度很好统计,用这一条扫描线的高度减去上一条扫描线的的高度即可,但有多少条竖线呢?
我们可以在线段树中添加三个成员,这样总共就会有五个:
struct node
{
int dis; //被覆盖的长度
int cnt; //被整体覆盖了几次
int ls; //左端点是否被覆盖
int rs; //右端点是否被覆盖
int num; //区间中总共有多少条竖线
};
接下来,考虑pushup()要怎么写
更新dis的部分在此不再赘述,详见最下面代码或者扫描线(一)
正确的更新竖线的代码是这样的
tre[nc].ls=tre[2*nc].ls;
tre[nc].rs=tre[2*nc+1].rs;
tre[nc].num=tre[2*nc].num+tre[2*nc+1].num;
if(tre[2*nc].rs&&tre[2*nc+1].ls)
{
tre[nc].num-=2;
}
关键点在if里边,画张图
如图所示,L到R的的两个子区间中,有两条竖线在和并之后消失了,其原因是这两条线段刚好覆盖了分点,因而,要加上if来保证其正确性
然后就是一个小细节,重边要先加后减,否则就会多统计重边,排序时在cmp中处理一下即可。
奉上代码
1 #include
2 #include
大家可能会发现这和(一)中的代码神似,没错,鄙人就是根据(一)中的代码加以修改的!!!!!!!!!!!!!!!
Original: https://www.cnblogs.com/Grharris/p/10392495.html
Author: Grharris
Title: 线段树扫描线(二)矩形周长 以hdu1828为例
原创文章受到原创版权保护。转载请注明出处:https://www.johngo689.com/578004/
转载文章受原作者版权保护。转载请注明原作者出处!