## 扫描线专题
扫描线是一种求 **矩形面积并**/ **周长并** 的好方法。

**扫描线**：假设有一条扫描线从一个图形的下方扫向上方（或者左方扫到右方），那么通过分析扫描线被图形截得的线段就能获得所要的结果。该过程可以用 **线段树** 进行加速。

https://www.luogu.com.cn/blog/paperghost/ls-xue-xi-bi-ji-note37-sao-miao-xian-line-sweep-algorithm

#### 一、面积并

**[$P5490$ 【模板】扫描线 ](https://www.cnblogs.com/littlehb/p/17654282.html)**

**[$POJ$ $1151$ $Atlantis$](http://poj.org/problem?id=1151)**

**[$AcWing$ $247$. 亚特兰蒂斯](https://www.cnblogs.com/littlehb/p/16164294.html)**

#### 二、周长并
**[$HDU$ $1828$ $Picture$](https://www.cnblogs.com/littlehb/p/17654258.html)**

**[$POJ1177$ $Picture$](http://poj.org/problem?id=1177)**



https://zhuanlan.zhihu.com/p/498450353

POJ2528
https://blog.csdn.net/DERITt/article/details/51037398

https://blog.csdn.net/qq_41765114/article/details/90179868?spm=1001.2101.3001.6650.14&utm_medium=distribute.pc_relevant.none-task-blog-2%7Edefault%7EBlogCommendFromBaidu%7ERate-14-90179868-blog-16995075.235%5Ev38%5Epc_relevant_anti_vip_base&depth_1-utm_source=distribute.pc_relevant.none-task-blog-2%7Edefault%7EBlogCommendFromBaidu%7ERate-14-90179868-blog-16995075.235%5Ev38%5Epc_relevant_anti_vip_base&utm_relevant_index=19


POJ2482
CF817F
CF377D



#### (3)、扫描线
[视频讲解](https://www.bilibili.com/video/BV1yo4y197Zd)


**[$AcWing$ $1228$. 油漆面积](https://www.cnblogs.com/littlehb/p/16163734.html)**
**【扫描线+线段树+面积合并】**

[$AcWing$ $247$. 亚特兰蒂斯](https://www.cnblogs.com/littlehb/p/16164294.html)  [扫描线+线段树+面积并+离散化] 

[$HDU5091$ $Beam$ $Cannon$](https://www.cnblogs.com/littlehb/p/16993823.html)  [扫描线+线段树+格点问题(含边界)] 

[$AcWing$ $248$. 窗外的星星](https://www.cnblogs.com/littlehb/p/16992576.html)  [扫描线+线段树+格点问题(去边界)] 

[$HDU4007$ $Dave$](http://acm.hdu.edu.cn/showproblem.php?pid=4007) [扫描线+线段树+格点问题(含边界)]