背景

试题来源：https://koi.or.kr/archives/。中文翻译做了少量本土化修改。

按照署名—非商业性使用—相同方式共享 4.0 协议国际版进行授权。

题目描述

在二维平面上的 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$ 个房屋的坐标。

输出格式

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

5 2
1 5
3 0
3 3
6 12
8 9

5

4 2
0 0
0 5
5 0
5 5

5

4 1
1 0
2 0
3 0
4 0

2

2 1
20 23
5 14

24

提示

限制条件

• 所有输入的数值均为整数。
• $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 完成