#P12655. [KOI 2023 Round 1] 避难所
[KOI 2023 Round 1] 避难所
题目背景
试题来源:https://koi.or.kr/archives/。中文翻译做了少量本土化修改。
按照署名—非商业性使用—相同方式共享 4.0 协议国际版进行授权。
题目描述
在二维平面上的 KOI 村庄里有 个房屋。每个第 个房屋的位置是 。
第 个房屋和第 个房屋之间的距离是 ,也就是两个房屋之间的距离是 X 坐标差和 Y 坐标差的和。例如,位于 的房屋与位于 的房屋之间的距离是 。
KOI 村庄计划在发生灾难时,在 个房屋里安装避难所,以便居民能够安全撤离。为了考虑所有居民的安全,计划选择 个房屋作为避难所,使得每个居民到达最近避难所的距离尽可能小,其中最远的距离要尽量小。
以下是 个房屋的位置,分别是 、、、 和 。
在这个村庄里,计划安装 个避难所。如果我们将避难所分别安装在 和 位置,剩下的 个房屋到最近避难所的距离分别是 、、,其中最远的距离是 。
但是,如果将避难所安装在 和 位置,最远的距离是 ,即位于 的房屋到 的距离为 。
无论如何安装避难所,最远的距离无法小于 ,因此我们要找出最小的最大距离。
给定 KOI 村庄中房屋的位置和安装避难所的数量,要求你输出在所有可能的安装方案中,最近的避难所和房屋之间的距离的最大值最小的情况下的最大距离。
输入格式
第一行包含两个整数 和 ,表示房屋的数量和避难所的数量。
接下来 行,每行包含两个整数 和 ,表示第 个房屋的坐标。
输出格式
输出一个整数,表示最小的最大距离。
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
提示
限制条件
- 所有输入的数值均为整数。
- 同一位置上不会有多个房屋,即 都是不同的。
子问题
- (5 分)
- (7 分),且所有房屋的 X 坐标分别为 且 Y 坐标为 0。
- (10 分)
- (18 分)
- (35 分),并且 且 且所有房屋的 Y 坐标为 0,即 X 坐标按升序排列。
- (25 分)
翻译由 ChatGPT-4o 完成