#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「 지름길

题目描述

NN 个城市分布在平面上的不同位置。这些城市用 11NN 的整数表示。

城市 ii 和城市 i+1i+1 之间有一条道路,记为 Ri(i=1,,N1)R_{i} (i=1, \ldots, N-1)。因此,总共有 N1N-1 条道路。对于每个 i=1,,N1i=1, \ldots, N-1,城市 ii 的坐标为 (xi,yi)\left(x_{i}, y_{i}\right),道路 RiR_{i} 的长度为 $\left|x_{i}-x_{i+1}\right|+\left|y_{i}-y_{i+1}\right|$。

城市 iijj 之间的路径 PP 是从 iijj 经过的道路集合。路径 PP 的长度是 PP 中所有道路长度的总和。我们对城市的直径感兴趣。直径是所有城市之间最短路径长度的最大值。当然,上述城市的直径等于城市 11 和城市 NN 之间路径的长度。

我们计划在上述城市中选择一对城市,在它们之间新建一条道路。记这条新道路为 RnewR_{\text{new}},如果 RnewR_{\text{new}} 连接城市 aabb,则 RnewR_{\text{new}} 的长度为 xaxb+yayb\left|x_{a}-x_{b}\right|+\left|y_{a}-y_{b}\right|。问题是如何选择 RnewR_{\text{new}} 使得城市的直径最小。

给定 NN 个城市的位置,编写一个程序,选择 RnewR_{\text{new}} 使城市的直径最小,并输出最小的直径值。

例如,下图中有 44 个城市和连接城市之间的 33 条道路(实线)。可以新建的道路有 33 条(1144 之间,1133 之间,4422 之间)。在这些候选中,如图所示,在 4422 之间新建一条道路(虚线),城市的直径为 66,这是最小值。

你需要为代码实现以下函数,并使用该函数提交答案。

long long shortcut(int N, long long X[], long long Y[]);

  • 参数 N 是城市的数量,X[0..N-1]Y[0..N-1] 分别表示每个城市的 xx 坐标和 yy 坐标。X[]Y[] 是大小为 NN 的数组,X[i]Y[i] 分别表示城市 i+1i+1xx 坐标和 yy 坐标。你需要使用该函数提交结果。返回值是新建道路后城市的最小直径。

你需要提交一份代码,该代码中实现以下函数:

long long shortcut(int N, long long X[], long long Y[]);

该函数应按照上述描述工作。当然,你可以创建其他函数并在内部使用。提交的代码不应执行输入输出操作或访问其他文件。

输入格式

示例评测程序按以下格式读取输入:

11 行:NNNN 表示城市的数量
2(N+1)2 \sim(N+1) 行:第 ii 行包含两个整数 xxyy,表示城市 i1i-1 的坐标 (x,y)(x, y)

输出格式

示例评测程序输出新建道路后城市的最小直径。

4
1 2
2 2
2 1
1 1

2
4
1 2
3 3
4 1
2 3

6

提示

对于所有输入数据,满足:

  • 3N2.51053 \leq N \leq 2.5\cdot 10^5
  • 109x,y10910^{9} \leq x, y \leq 10^{9}

详细子任务附加限制及分值如下表所示。

Subtask 分值 约束
11 44 N40N \leq 40
22 66 N100N \leq 100
33 1212 N300N \leq 300
44 2525 N2,000N \leq 2,000
55 4040 N50,000N \leq 50,000
66 1313 无附加限制