题目描述

题目译自 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)$

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

样例 1

输入

4
1 2
2 2
2 1
1 1

输出

2

样例 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}$

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

子任务	分值	附加限制
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	无附加限制