本题没有可用的提交语言。

题目描述

永仁市计划建设一个包含 $N$ 个公交站点的公交网络。每个公交站点位于街道拐角处，城市地图由大小相同的方形街区组成网格。需要从中选择两个站点作为枢纽站 $H_1$ 和 $H_2$，并满足以下条件：

1. 两个枢纽站之间建立直达公交线路。
2. 其余 $N-2$ 个站点直接连接到 $H_1$ 或 $H_2$（不能同时连接两个），且不与其他站点直接相连。

距离计算规则：

• 任意两站点间的距离为曼哈顿距离：$d(A,B) = |x_1 - x_2| + |y_1 - y_2|$。
• 若两站点 $A$ 和 $B$ 连接同一枢纽 $H$，则路线距离为 $d(A,H) + d(H,B)$。
• 若两站点 $A$ 和 $B$ 连接不同枢纽（$A$ 连 $H_1$，$B$ 连 $H_2$），则路线距离为 $d(A,H_1) + d(H_1,H_2) + d(H_2,B)$。

规划目标：

选择最优的枢纽组合 $H_1$ 和 $H_2$，使得在该公交网络中任意两站点间的最长路线距离尽可能短。若方案 $P$ 的最长路线短于方案 $Q$，则 $P$ 优于 $Q$。

输入格式

• 第一行：公交站点数 $N$（$2 \leq N \leq 500$）。
• 随后 $N$ 行：每行两个整数 $(x, y)$，表示站点坐标（$1 \leq x, y \leq 5000$）。
• 所有站点位置唯一。

输出格式

输出一个整数，表示最优枢纽选择方案下的最长路线最小长度。

样例输入

7
7 9
10 9
5 3
1 1
7 2
15 6
17 7

样例输出

25

样例解释

当选择站点5（坐标 $(7,2)$）和站点6（坐标 $(15,6)$）作为枢纽时：

• 站点2（坐标 $(10,9)$）与站点7（坐标 $(17,7)$）之间的路线距离达到最大值25。
• 不存在其他枢纽选择方案能使最长路线距离更短。

题目来源

2002年国际信息学奥林匹克竞赛（IOI 2002）