外观
Skip to content 查看源代码：
查看源代码：
FFMP-Ex13-solution.md
---
title: FFMP Ex13 解答
createTime: 2026/4/20
---
## 自交点数
我们知道平面图的欧拉公式 $V-E+F = 2$，由 $E = 2V$ 可知 $F = V + 2$。因此，问题转化为最大化路径的自交点数。
## 同向角
:::center
:::
如图，一个自交点总是对应唯一的一对（交错）同向角，而每对交错同向角最多对应一个自交点。从而转化为 [Ex 12] 的逆序对问题，可以用组合方法解决。
那有没有更优雅的方法呢？~~穿西装解题之类的方法不在考虑范围内。~~
## 扫描线
想象一根线从上到下扫描，记录线与路径交点的个数。
此时，线与路径交点成对出现、成对消失，而自交点数与成对出现/消失时，这对点所成的横线段会与它们之间的每一个点都形成一个自交点。
于是贪心地，我们令所有点的消失都在所有点出现之后。以逆时针为正方向，即向左的边都在向右的边之上。
## 反转变换
::::definition 反转变换
将第 $i$ 高的向右边与第 $n+1-i$ 高的向右边交换高度。将第 $i$ 高的向左边与第 $n+1-i$ 高的向左边交换高度。
如图：
:::center
:::
::::
根据扫描线得出的结论，只需讨论所有向左边都在向右边之上的情形，一条合法路径的反转变换结果仍是一条合法路径。接下来，我们来考虑变换前后的自交点数。
:::center
{width="500px"}
:::
如图，反转变换会将交错同向角与不交错同向角互相变换，从而变换前后的交点数不大于 $4\mathrm{C}_{n}^{2}$。
## 多边形自交点数下界
:::lemma
若 $n$ 边形的外角和为 $A$，自交点数为 $n$，则 $n \ge \dfrac{|A|}{2\pi} - 1$。
:::
::::definition 外角
这里的“外角”指将顶点顺次编号后，将 $\overrightarrow{P_{i-1}P_i}$ 以逆时针为正方向旋转至 $\overrightarrow{P_iP_{i+1}}$ 的有向旋转角主值（取 $(-\pi, \pi]$）。
:::center
{width=500px}
红色：逆时针，正外角；蓝色：顺时针，负外角。
图中的多边形不符合原始题意，仅为“外角”定义的演示。
:::
::::
:::proof
考虑对 $n$ 归纳，$n=0$ 时，根据简单多边形外角和定理，一定有 $|A| = 2\pi$，奠基成立。
假设命题对 $0,1,\dots,n-1$ 都成立，下证命题对 $n$ 成立：
由简单多边形外角和定理可知简单多边形的 $|A| = 2\pi$，于是$|A| > 2\pi$ 时多边形一定不是简单多边形，即至少有一个自交点，记作 $P$。
将整个多边形从 $P$ 分开，分成两个小多边形。记两个小多边形的外角和、自交点数分别为 $A_1, A_2; n_1, n_2$，显然
- $A = A_1 + A_2$
- $n = n_1 + n_2 + 1$
于是 $n = n_1 + n_2 + 1 \ge (|A_1| - 1) + (|A_2| - 1) + 1 \ge |A_1+A_2| - 1 = |A| - 1$，证毕。
:::
## 结论于此汇合
设最多有 $V$ 个自交点，最多的图形的经反转变换后有 $v$ 个自交点，于是 $v + V \le 2n(n-1)$。
根据 $v \ge n-1$，可知 $V \le 4\mathrm{C}_{n}^{2}-(n-1) = 2n^2-3n+1$。
注意到以下构造
:::center
:::
于是 $V_{\max} = 2n^2-3n+1$，即 $F_{\max} = 2n^2-3n+3$，~~233！~~