#P12655. [KOI 2023 Round 1] 避难所

[KOI 2023 Round 1] 避难所

题目背景

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

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

题目描述

在二维平面上的 KOI 村庄里有 NN 个房屋。每个第 ii 个房屋的位置是 (Xi,Yi)(X_i, Y_i)

ii 个房屋和第 jj 个房屋之间的距离是 XiXj+YiYj|X_i − X_j| + |Y_i − Y_j|,也就是两个房屋之间的距离是 X 坐标差和 Y 坐标差的和。例如,位于 (1,6)(1, 6) 的房屋与位于 (2,4)(2, 4) 的房屋之间的距离是 (21)+(64)=3(2 - 1) + (6 - 4) = 3

KOI 村庄计划在发生灾难时,在 KK 个房屋里安装避难所,以便居民能够安全撤离。为了考虑所有居民的安全,计划选择 KK 个房屋作为避难所,使得每个居民到达最近避难所的距离尽可能小,其中最远的距离要尽量小。

以下是 55 个房屋的位置,分别是 (1,5)(1, 5)(3,0)(3, 0)(3,3)(3, 3)(6,12)(6, 12)(8,9)(8, 9)

在这个村庄里,计划安装 22 个避难所。如果我们将避难所分别安装在 (3,0)(3, 0)(1,5)(1, 5) 位置,剩下的 33 个房屋到最近避难所的距离分别是 3311111212,其中最远的距离是 1212

但是,如果将避难所安装在 (3,3)(3, 3)(6,12)(6, 12) 位置,最远的距离是 55,即位于 (8,9)(8, 9) 的房屋到 (6,12)(6, 12) 的距离为 55

无论如何安装避难所,最远的距离无法小于 55,因此我们要找出最小的最大距离。

给定 KOI 村庄中房屋的位置和安装避难所的数量,要求你输出在所有可能的安装方案中,最近的避难所和房屋之间的距离的最大值最小的情况下的最大距离。

输入格式

第一行包含两个整数 NNKK,表示房屋的数量和避难所的数量。

接下来 NN 行,每行包含两个整数 XiX_iYiY_i,表示第 ii 个房屋的坐标。

输出格式

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

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

提示

限制条件

  • 所有输入的数值均为整数。
  • 1K31 \leq K \leq 3
  • KN50K \leq N \leq 50
  • 0Xi100,0000 \leq X_i \leq 100,000
  • 0Yi100,0000 \leq Y_i \leq 100,000
  • 同一位置上不会有多个房屋,即 (X1,Y1),(X2,Y2),,(XN,YN)(X_1, Y_1), (X_2, Y_2), \dots, (X_N, Y_N) 都是不同的。

子问题

  1. (5 分)N=K+1N = K + 1
  2. (7 分)K=1K = 1,且所有房屋的 X 坐标分别为 Xi=iX_i = i 且 Y 坐标为 0。
  3. (10 分)K=1K = 1
  4. (18 分)K=2K = 2
  5. (35 分)K=3K = 3,并且 1iN11 \leq i \leq N-1Xi<Xi+1X_i < X_{i+1} 且所有房屋的 Y 坐标为 0,即 X 坐标按升序排列。
  6. (25 分)K=3K = 3

翻译由 ChatGPT-4o 完成