P12655 [KOI 2023 Round 1] 避难所

试题来源：。中文翻译做了少量本土化修改。 按照[署名—非商业性使用—相同方式共享 4.0 协议国际版](https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh-hans)进行授权。

在二维平面上的 KOI 村庄里有 $N$ 个房屋。每个第 $i$ 个房屋的位置是 $(X_i, Y_i)$。  第 $i$ 个房屋和第 $j$ 个房屋之间的距离是 $|X_i − X_j| + |Y_i − Y_j|$，也就是两个房屋之间的距离是 X 坐标差和 Y 坐标差的和。例如，位于 $(1, 6)$ 的房屋与位于 $(2, 4)$ 的房屋之间的距离是 $(2 - 1) + (6 - 4) = 3$。 KOI 村庄计划在发生灾难时，在 $K$ 个房屋里安装避难所，以便居民能够安全撤离。为了考虑所有居民的安全，计划选择 $K$ 个房屋作为避难所，使得每个居民到达最近避难所的距离尽可能小，其中最远的距离要尽量小。 以下是 $5$ 个房屋的位置，分别是 $(1, 5)$、$(3, 0)$、$(3, 3)$、$(6, 12)$ 和 $(8, 9)$。  在这个村庄里，计划安装 $2$ 个避难所。如果我们将避难所分别安装在 $(3, 0)$ 和 $(1, 5)$ 位置，剩下的 $3$ 个房屋到最近避难所的距离分别是 $3$、$11$、$12$，其中最远的距离是 $12$。  但是，如果将避难所安装在 $(3, 3)$ 和 $(6, 12)$ 位置，最远的距离是 $5$，即位于 $(8, 9)$ 的房屋到 $(6, 12)$ 的距离为 $5$。 无论如何安装避难所，最远的距离无法小于 $5$，因此我们要找出最小的最大距离。  给定 KOI 村庄中房屋的位置和安装避难所的数量，要求你输出在所有可能的安装方案中，最近的避难所和房屋之间的距离的最大值最小的情况下的最大距离。

第一行包含两个整数 $N$ 和 $K$，表示房屋的数量和避难所的数量。 接下来 $N$ 行，每行包含两个整数 $X_i$ 和 $Y_i$，表示第 $i$ 个房屋的坐标。

输出一个整数，表示最小的最大距离。

**限制条件** - 所有输入的数值均为整数。 - $1 \leq K \leq 3$ - $K \leq N \leq 50$ - $0 \leq X_i \leq 100,000$ - $0 \leq Y_i \leq 100,000$ - 同一位置上不会有多个房屋，即 $(X_1, Y_1), (X_2, Y_2), \dots, (X_N, Y_N)$ 都是不同的。 **子问题** 1. （5 分）$N = K + 1$ 2. （7 分）$K = 1$，且所有房屋的 X 坐标分别为 $X_i = i$ 且 Y 坐标为 0。 3. （10 分）$K = 1$ 4. （18 分）$K = 2$ 5. （35 分）$K = 3$，并且 $1 \leq i \leq N-1$ 且 $X_i < X_{i+1}$ 且所有房屋的 Y 坐标为 0，即 X 坐标按升序排列。 6. （25 分）$K = 3$ 翻译由 ChatGPT-4o 完成