AT_joigsp2025_c 救急車 (Ambulance)

IOI 王国拥有一个由 $L$ 行 $L$ 列排列的方格组成的领土。从上往下第 $i$ 行（$1 \leq i \leq L$）、从左往右第 $j$ 列（$1 \leq j \leq L$）的格子记作 $(i,j)$。 最近，IOI 王国出现了许多因传染病倒下的患者，民众呼吁加强医疗设施。因此，IOI 王国的国王“比太郎”决定在 $(1, 1)$、$(1, L)$、$(L, 1)$、$(L, L)$ 这四个位置各建一座医院，并为每家医院配备一辆救护车。 谨慎的比太郎打算模拟实际发生救援请求时的情况。设想的场景是，时刻 $0$ 时有 $N$ 位患者发出救援请求，他想知道能否在时刻 $T$ 之前将所有患者都送到任意一家医院。第 $k$ ($1 \leq k \leq N$) 位患者位于 $(X_k, Y_k)$。 救护车按如下规则运送患者： - 每辆救护车可在时刻 $0$ 之后出发，从对应医院出发到达患者所在格，将患者搭载归医院，再返回医院继续接送下一位病人。 - 每辆救护车一次最多只能搭载一位患者。 - 每辆救护车只能将患者运送回其对应医院，不能在其他无医院的格子卸下患者。 - 每辆救护车每次在上下左右相邻的格之间移动需要 $1$ 单位时间，搭载和卸下患者消耗的时间可忽略不计。 - 不同医院的救护车可以同时停留在同一个格子内。 由于比太郎无法得知自己设想场景的最终结果，因此请你编程帮他判断，在给定的领土大小和场景条件下，是否可以在时刻 $T$ 之前将所有患者送到任一医院。

输入通过标准输入给出，格式如下： > $L$ $N$ $T$ $X_1$ $Y_1$ $X_2$ $Y_2$ $\vdots$ $X_N$ $Y_N$

如果比太郎预想的场景下，能在时刻 $T$ 之前将所有患者送到任意一家医院，输出 `Yes`，否则输出 `No`，输出占一行。

## 子任务 1.（$5$ 分）$T \leq 50$。 2.（$10$ 分）$T \leq 160$。 3.（$8$ 分）$N \leq 10$。 4.（$21$ 分）$N \leq 20$。 5.（$17$ 分）$N \leq 45$，$L$ 为奇数且 $Y_k = \frac{L+1}{2}$（$1 \leq k \leq N$）。 6.（$29$ 分）$N \leq 45$。 7.（$10$ 分）没有额外约束。 --- ## 样例解释1 可以将第 $1$、$2$ 位患者送到 $(1,1)$ 的医院，第 $3$ 位送到 $(1,L)$ 的医院，第 $4$ 位送到 $(L,L)$ 的医院，在时刻 $8$ 之前可全部送达，所以输出 `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,2,3,4,6,7$ 的约束。 --- ## 样例解释2 无法在时刻 $19$ 之前将所有患者送达任意一家医院，因此输出 `No`。 本样例满足全部子任务约束。 --- ## 样例解释3 本样例满足子任务 $1,2,3,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 \leq L$（$1 \leq k \leq N$） - $1 \leq Y_k \leq L$（$1 \leq k \leq N$） - $(X_k, Y_k)$ 不为 $(1,1)$、$(1,L)$、$(L,1)$、$(L,L)$ 之一（$1 \leq k \leq N$）。 - 所有输入均为整数。 由 ChatGPT 5 翻译