#P11707. 「KTSC 2020 R1」捷径
「KTSC 2020 R1」捷径
题目背景
请使用 C++17 或 C++20 提交本题
你需要在程序开头加入如下代码:
#include<vector>
long long shortcut(int N, std::vector<long long> X, std::vector<long long> Y);
题目译自 2020년도 국제정보올림피아드 대표학생 선발고사 - 1차 선발고사 T3「 지름길」
题目描述
有 个城市分布在平面上的不同位置。这些城市用 到 的整数表示。
城市 和城市 之间有一条道路,记为 。因此,总共有 条道路。对于每个 ,城市 的坐标为 ,道路 的长度为 $\left|x_{i}-x_{i+1}\right|+\left|y_{i}-y_{i+1}\right|$。
城市 和 之间的路径 是从 到 经过的道路集合。路径 的长度是 中所有道路长度的总和。我们对城市的直径感兴趣。直径是所有城市之间最短路径长度的最大值。当然,上述城市的直径等于城市 和城市 之间路径的长度。
我们计划在上述城市中选择一对城市,在它们之间新建一条道路。记这条新道路为 ,如果 连接城市 和 ,则 的长度为 。问题是如何选择 使得城市的直径最小。
给定 个城市的位置,编写一个程序,选择 使城市的直径最小,并输出最小的直径值。
例如,下图中有 个城市和连接城市之间的 条道路(实线)。可以新建的道路有 条( 和 之间, 和 之间, 和 之间)。在这些候选中,如图所示,在 和 之间新建一条道路(虚线),城市的直径为 ,这是最小值。
你需要为代码实现以下函数,并使用该函数提交答案。
long long shortcut(int N, long long X[], long long Y[]);
- 参数
N
是城市的数量,X[0..N-1]
和Y[0..N-1]
分别表示每个城市的 坐标和 坐标。X[]
和Y[]
是大小为 的数组,X[i]
和Y[i]
分别表示城市 的 坐标和 坐标。你需要使用该函数提交结果。返回值是新建道路后城市的最小直径。
你需要提交一份代码,该代码中实现以下函数:
long long shortcut(int N, long long X[], long long Y[]);
该函数应按照上述描述工作。当然,你可以创建其他函数并在内部使用。提交的代码不应执行输入输出操作或访问其他文件。
输入格式
示例评测程序按以下格式读取输入:
第 行:, 表示城市的数量
第 行:第 行包含两个整数 和 ,表示城市 的坐标
输出格式
示例评测程序输出新建道路后城市的最小直径。
4
1 2
2 2
2 1
1 1
2
4
1 2
3 3
4 1
2 3
6
提示
对于所有输入数据,满足:
详细子任务附加限制及分值如下表所示。
Subtask | 分值 | 约束 |
---|---|---|
无附加限制 |