题解 #9037 Ancient Maps, Hidden Danger
Diaоsi
·
·
算法·理论
Ancient Maps, Hidden Danger
给出 m\,(m\leq 30) 个不交简单多边形（总点数 n\leq 90），从无限远的所有方向打光，求出多边形遮挡的阴影面积。
记录一下怎么完成这个毒瘤题的。阴影面积不好算，考虑算被照亮的面积，如果点 P 能被照亮，那么可以稍微把光线旋转一些，使得照亮 P 的光线恰好经过一个多边形的顶点 A。于是可以把 P 当成是 A 照亮的。
思考点 P 被点 A 照亮的充分条件，需要满足
- 线段 \overline{AP} 不与任何边相交，不经过任何多边形内部
- 射线 \overrightarrow{AP^\prime} 不与任何边相交/经过多边形内部，P^\prime 是 P 关于 A 的对称点
枚举每个顶点 A 计算它能够照亮的区域。根据上面的两个条件，把所有的顶点及其关于 A 的对称点以 A 为原点做极角排序，每个极角区间一定是极小的——要么全被照亮要么全部无法被照亮。
接下来计算一个极角区间能够被照亮多少，假设这个区间的两个向量是 \overrightarrow{AB} 和 \overrightarrow{AC}。先判断射线 \overrightarrow{AB^\prime} 和 \overrightarrow{AC^\prime} 是否在多边形外，可以在射线方向上选择一个略微超出值域范围的点，然后用判断线段在多边形外的方法进行判断。
如果反向射线没有相交，那么找到与 \overrightarrow{AB},\overrightarrow{AC} 相交的一条边，设交点分别为 E,F，判断 \overline{AE} 和 \overline{AF} 是否在多边形外。两条射线会相交在同一条边上，如果没有交可以跳过这个区间，说明这个区域会被其他点照亮。若能够找到（唯一）一对符合条件的 E,F，那么 \triangle AEF 就是一个会被 A 照亮的区域。
以多边形的每个顶点为原点，能够找出 \mathcal{O}(n^2) 个被照亮的三角形。将这些三角形取并集就是所有被照亮的区域，然后用全集 - 多边形面积 - 照亮区域就是答案。这里的全集是所有点形成的凸包的面积，因为在上面的算法中每条光线都是由两个整点确定的，那么外侧的边就是凸包的边。
然后就是一些 corner case，大概有这些：
- 怎么判断线段在多边形外？把逆时针多边形改成顺时针，然后判断线段是否在多边形内部就行；需要处理好线段恰好跨过顶点/和边界共线的情况
- 极角扫描线的时候注意区间退化的情况
- 如果有多边形是三角形，上面的算法可能会把这个三角形当作照亮面积；一个不用动脑的解决方案是把多边形也丢在一起求并
- 三角形的顶点是两条直线的交点，求三角形并还要再次求交点，两重交点可能会爆精度；注意到三角形的边的直线是两个整点产生的，拿这两个整点用于后续求交可以优化精度
时间复杂度瓶颈在于求面积并，由于有 \mathcal{O}(n^2) 个三角形，因此时间复杂度为 \mathcal{O}(n^4\log n)。官解给出的面积并的做法是：对所有线段交点建平面图然后单独计算每个 Cell 的面积，不需要每次都排序因此十分高效；实际上常规扫描线做法的效率也比较可观，可以在 ~3000ms 的时间通过。
提交记录