HDU 1542 Atlantis

Segment-Tree, Sweep line algorithm

Posted by 闫鸿宇 on August 7, 2016 1 minute read ∼ Tagged with : segment-tree • sweep-line-algorithm ∼ Filed in : study

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

解决方法：
将每个矩形的左右边看做两个事件，将所有事件按x升序排序，用线段树维护当前被覆盖的宽度，与两次事件之间的距离（长度）相乘，从而求出所有的矩形并的大小。

代码： HDU 1542

By 闫鸿宇

An undergraduate at Shanghai Jiao Tong University who studies CS.