注意事项

在 LibreOJ 上，由于语言限制，目前只支持以下语言的提交：

• C++（标准为 C++ 17 及以上）

请在提交源代码前添加 #include "shortcut.h"。

题目描述

题目译自 2020년도 국제정보올림피아드 대표학생 선발고사 - 1차 선발고사 T3 「지름길」

有 $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$ 坐标。你需要使用该函数提交结果。返回值是新建道路后城市的最小直径。

实现细节

你需要提交一个名为 shortcut.cpp 的文件，该文件中实现以下函数：

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)$

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

4
1 2
2 2
2 1
1 1

2

4
1 2
3 3
4 1
2 3

6

数据范围与提示

对于所有输入数据，满足：

• $3 \leq N \leq 2.5\cdot 10^5$
• $10^{9} \leq x, y \leq 10^{9}$

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