P11707 「KTSC 2020 R1」捷径

**请使用 C++17 或 C++20 提交本题** 你需要在程序开头加入如下代码： ```cpp #include long long shortcut(int N, std::vector X, std::vector Y); ``` 题目译自 [2020년도 국제정보올림피아드 대표학생 선발고사 - 1차 선발고사](https://www.ioikorea.kr/archives/ioitst/2020/) T3「 [지름길](https://assets.ioikorea.kr/ioitst/2020/1/shortcut/shortcut_statement.pdf)」

有 $N$ 个城市分布在平面上的不同位置。这些城市用 $1$ 到 $N$ 的整数表示。 城市 $i$ 和城市 $i+1$ 之间有一条道路，记为 $R_{i} (i=1, \ldots, N-1)$。因此，总共有 $N-1$ 条道路。对于每个 $i=1, \ldots, N-1$，城市 $i$ 的坐标为 $\left(x_{i}, y_{i}\right)$，道路 $R_{i}$ 的长度为 $\left|x_{i}-x_{i+1}\right|+\left|y_{i}-y_{i+1}\right|$。 城市 $i$ 和 $j$ 之间的路径 $P$ 是从 $i$ 到 $j$ 经过的道路集合。路径 $P$ 的长度是 $P$ 中所有道路长度的总和。我们对城市的直径感兴趣。直径是所有城市之间最短路径长度的最大值。当然，上述城市的直径等于城市 $1$ 和城市 $N$ 之间路径的长度。 我们计划在上述城市中选择一对城市，在它们之间新建一条道路。记这条新道路为 $R_{\text{new}}$，如果 $R_{\text{new}}$ 连接城市 $a$ 和 $b$，则 $R_{\text{new}}$ 的长度为 $\left|x_{a}-x_{b}\right|+\left|y_{a}-y_{b}\right|$。问题是如何选择 $R_{\text{new}}$ 使得城市的直径最小。 给定 $N$ 个城市的位置，编写一个程序，选择 $R_{\text{new}}$ 使城市的直径最小，并输出最小的直径值。 例如，下图中有 $4$ 个城市和连接城市之间的 $3$ 条道路（实线）。可以新建的道路有 $3$ 条（$1$ 和 $4$ 之间，$1$ 和 $3$ 之间，$4$ 和 $2$ 之间）。在这些候选中，如图所示，在 $4$ 和 $2$ 之间新建一条道路（虚线），城市的直径为 $6$，这是最小值。  你需要为代码实现以下函数，并使用该函数提交答案。 `long long shortcut(int N, long long X[], long long Y[]);` - 参数 `N` 是城市的数量，`X[0..N-1]` 和 `Y[0..N-1]` 分别表示每个城市的 $x$ 坐标和 $y$ 坐标。`X[]` 和 `Y[]` 是大小为 $N$ 的数组，`X[i]` 和 `Y[i]` 分别表示城市 $i+1$ 的 $x$ 坐标和 $y$ 坐标。你需要使用该函数提交结果。返回值是新建道路后城市的最小直径。 你需要提交一份代码，该代码中实现以下函数： `long long shortcut(int N, long long X[], long long Y[]);` 该函数应按照上述描述工作。当然，你可以创建其他函数并在内部使用。提交的代码不应执行输入输出操作或访问其他文件。

示例评测程序按以下格式读取输入： 第 $1$ 行：$N$，$N$ 表示城市的数量 第 $2 \sim(N+1)$ 行：第 $i$ 行包含两个整数 $x$ 和 $y$，表示城市 $i-1$ 的坐标 $(x, y)$

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

对于所有输入数据，满足： - $3 \leq N \leq 2.5\cdot 10^5$ - $-10^{9} \leq x, y \leq 10^{9}$ 详细子任务附加限制及分值如下表所示。 | Subtask | 分值 | 约束 | | :----------: | :----------: | :----------: | |$1$|$4$|$N \leq 40$| |$2$|$6$|$N \leq 100$| |$3$|$12$|$N \leq 300$| |$4$|$25$|$N \leq 2,000$| |$5$|$40$|$N \leq 50,000$| |$6$|$13$|无附加限制|