hdu 1255 覆盖的面积 (扫描线+线段树 求矩形面积交)

题目链接

题意:

求n(1000)个矩形的面积交,也就是至少有2个矩形覆盖的区域的面积

思路:

矩形面积并_hdu1542解题报告    类似

面积并问题中,线段树len维护的是至少覆盖一次的区域的长度

在面积交的问题中,我们需要多维护一个”至少覆盖两次的区域的长度”的域(设为double two;)

同时也要维护至少覆盖一次的区域的长度(设为double one;),是因为至少覆盖两次的区域的长度可以由至少覆盖一次的区域长度得到(好像是废话)

PushUp的时候要格外注意当前节点被完整覆盖一次的情况。

此时tree[rt].two 可以由两个子区间的one的情况想加得到

因为rt节点被完整覆盖了至少一次,那么如果rt儿子区间中被覆盖了至少一次,对于rt区间中被rt<<1和rt<<1|1覆盖至少一次的区间在对于rt区间就已经覆盖了至少2次

 

以及要注意题意说得不够清楚。最后保留2位小数是四舍五入。

读入的实际上是左下角和右上角的点。。。。

 

 

 

作者: CrazyKK

ex-ACMer@hust,stackoverflow-engineer@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz