2020-2021:teams:legal_string:王智彪:扫描线
| 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:王智彪:扫描线 [2021/08/04 11:49] 王智彪 创建 |
2020-2021:teams:legal_string:王智彪:扫描线 [2021/08/04 11:52] (当前版本) 王智彪 |
||
|---|---|---|---|
| 行 3: | 行 3: | ||
| ===== 算法思想 ===== | ===== 算法思想 ===== | ||
| - | 问题引入：给n个矩形的左下角和右上角坐标 求并集覆盖的总面积 | + | 问题引入：给 $n$ 个矩形的左下角和右上角坐标 求并集覆盖的总面积 |
| - | 复杂度O(nlogn) | + | 复杂度 $O(nlogn)$ |
| - | 比如按照横坐标从左到右扫，横坐标小的为1，横坐标大的为-1，面积就是相邻横坐标的差乘以当前区间有多少覆盖是正数的（毕竟不可能是负数）。这个线段树维护一下就行了。遇到1或者-1都交给线段树update就可以了。 | + | 比如按照横坐标从左到右扫，横坐标小的为 $1$ ，横坐标大的为 $-1$ ，面积就是相邻横坐标的差乘以当前区间有多少覆盖是正数的（毕竟不可能是负数）。这个线段树维护一下就行了。遇到 $1$ 或者 $-1$ 都交给线段树 $update$ 就可以了。 |
| - | 周长笨方法就是作两边扫描线，横纵各一次，周长是相邻两个阶段覆盖区域的绝对值之差，需要画个图看一下。<delete>但我觉得笨方法看起来更好想不是吗</delete> | + | 周长笨方法就是作两边扫描线，横纵各一次，周长是相邻两个阶段覆盖区域的绝对值之差，需要画个图看一下。 |
| + | |||
| + | 但我觉得笨方法看起来更好想不是吗 $(×)$ | ||
| ===== 代码练习 ===== | ===== 代码练习 ===== | ||
2020-2021/teams/legal_string/王智彪/扫描线.1628048969.txt.gz · 最后更改: 2021/08/04 11:49 由 王智彪
