AT_joisp2025_d 救急車 (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$ 名患者； - 每辆救护车只能将患者送回自身所在医院，且不能在没有医院的格子下车； - 每辆救护车每次能在上下左右方向中任一相邻格子移动 $1$ 个单位时间，接送病人时间可忽略； - 配备在不同医院的救护车可以同时出现在同一格子上。 由于比太郎无法事先得知模拟结果，所以请你替他判断：给定 IOI 王国的版图规模和模拟情景信息，是否能够在时刻 $T$ 之前把所有患者送达某间医院。

输入为以下格式，经标准输入读入： > $L$ $N$ $T$ $X_1$ $Y_1$ $X_2$ $Y_2$ $\vdots$ $X_N$ $Y_N$

如果能在比太郎设想的情景下，于时刻 $T$ 前将所有患者成功运送到任一医院，则输出 `Yes`，否则输出 `No`。

## 小子任务 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}$（$1 \leq k \leq N$）。 6. （$31$ 分）$N \leq 45$。 7. （$19$ 分）无更多约束。 --- ## 样例解释 1 将第 $1$、$2$ 名患者送到 $(1, 1)$ 的医院，将第 $3$ 名患者送到 $(1, 6)$ 的医院，将第 $4$ 名患者送到 $(6, 6)$ 的医院，即可在时刻 $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 10000$。 - $1 \leq N \leq 160$。 - $1 \leq T \leq 20000$。 - $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 翻译