P11986 [JOIST 2025] 救护车 / Ambulance

由于评测机性能差距，本题增加 1 秒时限。

IOI 王国被表示为一个 $L$ 行 $L$ 列的方形网格。行从上到下编号为 $1, 2, \dots, L$，列从左到右编号为 $1, 2, \dots, L$。 位于第 $i$ 行（$1 \leq i \leq L$）和第 $j$ 列（$1 \leq j \leq L$）的单元格记为 $(i, j)$。 由于近期疫情扩散，国王比太郎决定在网格的四个角落（单元格 $(1, 1)$、$(1, L)$、$(L, 1)$ 和 $(L, L)$）各建造一所医院，每所医院配备一辆救护车。救护车运输规则如下： - 救护车可在时间 $0$ 或之后开始移动。 - 救护车会重复以下步骤（可能 $0$ 次）： - 从所属医院出发 $\to$ 移动到患者位置 $\to$ 接载患者 $\to$ 返回医院并放下患者。 - 每辆救护车一次**最多**运送 $1$ 名患者。 - 救护车只能将患者送回其初始所属医院，**不可在其他位置放下患者**。 - 救护车每次移动到四连通单元格（上下左右）耗时 $1$ 单位时间。接载和放下患者的耗时忽略。 - 不同医院的救护车可同时占据同一单元格。 已知第 $k$ 名患者位于 $(X_k, Y_k)$，判断是否所有患者都能在时间 $T$ 内被运送到任意医院。

如下所示： > $L$ $N$ $T$\ > $X_1$ $Y_1$\ > $X_2$ $Y_2$\ > $\vdots$\ > $X_N$ $Y_N$

若所有患者可在时间 $T$ 内被送医，输出 $\texttt{Yes}$； 否则输出 $\texttt{No}$。

### 样例解释 #### 样例 $1$ 解释 - 将第 $1$ 和第 $2$ 个病人送往位于 $(1, 1)$ 的医院； - 将第 $3$ 个病人送往位于 $(1, 6)$ 的医院； - 将第 $4$ 个病人送往位于 $(6, 6)$ 的医院。 这样，所有病人都可以在第 $8$ 个时间点被送往医院，因此输出 $\texttt{Yes}$。 例如，如果停靠在 $(1, 1)$ 医院的救护车按照以下顺序移动，它可以在第 $8$ 个时间点之前将第 $1$ 和第 $2$ 个病人都送到医院。 | 时间 | 救护车状态 | |:---:|------------------------------------------------| | $0$ | 从单元格 $(1, 1)$ 出发 | | $1$ | 到达单元格 $(2, 1)$ | | $2$ | 到达单元格 $(2, 2)$，接上第 2 个病人，出发 | | $3$ | 到达单元格 $(1, 2)$ | | $4$ | 到达单元格 $(1, 1)$，放下第 2 个病人，出发 | | $5$ | 到达单元格 $(1, 2)$ | | $6$ | 到达单元格 $(1, 3)$，接上第 1 个病人，出发 | | $7$ | 到达单元格 $(1, 2)$ | | $8$ | 到达单元格 $(1, 1)$，放下第 1 个病人 | 该样例满足子任务 $1\sim 4,6,7$ 的限制。 #### 样例 $2$ 解释 可以证明不可能做到，所以输出 $\texttt{No}$。 该样例满足所有子任务的限制。 #### 样例 $3$ 解释 该样例满足子任务 $1\sim 4,6,7$ 的限制。 #### 样例 $4$ 解释 该样例满足子任务 $4,6,7$ 的限制。 ### 数据范围 - $3 \leq L \leq 10\,000$； - $1 \leq N \leq 160$； - $1 \leq T \leq 20\,000$； - $1 \leq X_k, Y_k \leq L$； - $(X_k, Y_k)$ 不与 $(1, 1), (1, L), (L, 1), (L, L)$ 的任意一个相等； - 所有输入值为整数。 ### 子任务 | 子任务 | 分数 | 特殊性质 | |:--:| :-:| - | | $1$ | $4 $ | $T \leq 50$ | | $2$ | $8 $ | $T \leq 160$ | | $3$ | $5 $ | $N \leq 10$ | | $4$ | $18$ | $N \leq 20$ | | $5$ | $15$ | $N \leq 45$，$L$ 为奇数，且所有患者满足 $Y_k = \frac{L+1}{2}$ | | $6$ | $31$ | $N \leq 45$ | | $7$ | $19$ | / |