给出 $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 的时间通过。