标签为 [扫描线] 的文章

HDU1828 Picture

题目大意 给定n个矩形(边平行于坐标轴),求被矩形覆盖图形的周长。 Solution 我们可以分别统计与x轴,y轴平行的周长之和。计算每条线段对答案的贡献。如果这条线段的某几段在被覆盖的图形外面,就可以加入答案。 例如对于平行于y轴的线段。用扫描线的方法,从左往右依次扫描,扫到左边的一条线段时,把整个区间整体+1,扫到右边的线段时,把整个区间整体-1。而操作时值是否为零发生变化的点,就是这条线段在被覆盖图形外面的点,也就是这条线段对答案的贡献。用线段树维护就可以。由于加上和减去的区间是一样的,甚至不用在修改 ......