HDU 1255 覆盖的面积

Segment-Tree, Sweep line algorithm

Posted by 闫鸿宇 on August 7, 2016   1 minute read ∼ Tagged with  :   •  ∼ Filed in  : 

给定平面上一组矩形，求面积交

解决方法： 与 HDU 1542 类似，同样将每个矩形的左右边看做两个事件，将所有事件按x升序排序，用线段树维护当前被多次覆盖的宽度，（嗯其实就是将阈值从1改成2），与长度乘一乘就可以求出来矩形面积交的大小。
代码：HDU 1255


Share this post

闫鸿宇's photo

By

An undergraduate at Shanghai Jiao Tong University who studies CS.