矩形面积并、矩形面积交、矩形周长并（线段树、扫描线总结）(转载） - jxr041100 - 博客园
- 离散化: 这些技巧都是老生常谈的了, 不然浮点数怎么建树, 离散化x坐标就可以了
- 扫描线: 首先把矩形按y轴分成两条边, 上边和下边, 对x轴建树, 扫描线可以看成一根平行于x轴的直线.
从y=0开始往上扫, 下边表示要计算面积+1, 上边表示已经扫过了−1, 直到扫到最后一条平行于x轴的边
但是真正在做的时候, 不需要完全模拟这个过程, 一条一条边地插入线段树就好了 - 线段树: 用于动态维护扫描线在往上走时, x轴哪些区域是有合法面积的
- ps:这种线段树是不用lazy的, 因为不用push_down, 为啥不用push_down, 因为没有查询操作
-
扫描线扫描的过程（建议配合代码模拟）
ps:无论说的再好,都不如自己在纸上模拟一遍扫描的过程,我自己学的时候模拟了很多遍
以下图转载自@kk303的博客
Read full article from 矩形面积并、矩形面积交、矩形周长并（线段树、扫描线总结）(转载） - jxr041100 - 博客园
No comments:
Post a Comment