huanghai
/
python
1
0
Fork 0
Code Issues Pull Requests Packages Projects Releases Wiki Activity
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
Branches Tags
${ item.name }
Create tag ${ searchTerm }
Create branch ${ searchTerm }
from 'main'
${ noResults }
python/TangDou/AcWing/SegmentTree/扫描线专题.md

2.1 KiB
Raw Permalink Blame History

扫描线专题

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

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

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

一、面积并

P5490 【模板】扫描线

POJ 1151 Atlantis

AcWing 247. 亚特兰蒂斯

二、周长并

HDU 1828 Picture

POJ1177 Picture

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)、扫描线

视频讲解

AcWing 1228. 油漆面积 【扫描线+线段树+面积合并】

AcWing 247. 亚特兰蒂斯 [扫描线+线段树+面积并+离散化]

HDU5091 Beam Cannon [扫描线+线段树+格点问题(含边界)]

AcWing 248. 窗外的星星 [扫描线+线段树+格点问题(去边界)]

HDU4007 Dave [扫描线+线段树+格点问题(含边界)]