查看源代码：
FFMP-Ex7-solution.md

---
title: 题解 - 我会看见，飞萤之火
createTime: 2025/5/31
categories:
    - study
tags:
    - maths
    - FFMP
---

显然代价 $c \ge 1$，下证这个下界能取到。

$c = 1$ 要求直线两两不平行。考虑如何将点对 $(S, D)$ 从 (茧, 星星) 点对变为 (萤火虫, 茧) 点对。

一种直接的想法是直接作连接两点的直线，然而这可能与已有的直线平行。于是考虑取一个中继点 $T$.

$T$ 必须满足以下三条约束：

$$
\begin{gather}
ST \nparallel l \in L, \\
TD \nparallel l \in L, \\
T \notin l \in L.
\end{gather}
$$

其中 $L$ 为使用过的直线集。

:::note Kim Jong-un 引理
无限集与有限集的差集仍是无限集。
:::

由金正恩引理，过 $S$ 总是存在不与任意用过的直线平行的直线，满足约束 $(1)$  
再由金正恩引理，直线 $m$ 上一定存在符合要求的 $T$ 满足约束 $(2)$.

于是，为每一个点编号（如按照逆时针螺旋），每次转移到编号最小的星星处。如此，编号为 $i$ 的点总会在 $2i$ 步内变为萤火虫。