题目背景

试题来源：https://koi.or.kr/archives/。中文翻译做了少量本土化修改。

按照署名—非商业性使用—相同方式共享 4.0 协议国际版进行授权。

题目描述

在二维平面上有 $N$ 个不同的点。对于每个 $1 \le i \le N$ 的 $i$，第 $i$ 个点的坐标为 $(x_i, y_i)$。

等腰三角形是指三条边中有两条边长度相等的三角形。直角三角形是指一个内角为直角 ($90^\circ$) 的三角形。直角三角形的斜边是指直角三角形中与直角相对的边，也是长度最长的边。等腰直角三角形是指既是直角三角形又是等腰三角形的三角形。即，三角形的一个内角为直角，且除斜边外的两条直角边长度相等的三角形。

请编写一个程序，找出满足以下两个条件的所有等腰直角三角形中，斜边长度最短的那个，并输出其斜边长度。

• $N$ 个点 $(x_1, y_1), (x_2, y_2), \cdots, (x_N, y_N)$ 都位于等腰直角三角形的边界（边上）或其内部。如果某个点位于等腰直角三角形的顶点上，也视为位于边界上。
• 斜边与 $x$ 轴平行。也就是说，等腰直角三角形斜边的两个端点的 $y$ 坐标相同。这意味着只有如下图所示的两种等腰直角三角形满足条件：直角顶点在斜边上方的，和直角顶点在斜边下方的。

例如，假设给定如下图所示的 5 个点：$(0, -1), (2, 4), (4, -1), (-1, 2), (3, 1)$。点本身没有大小，但在图中为了方便观察，用圆形表示。

在直角顶点位于斜边上方的等腰直角三角形中，斜边最短的是如下图所示的，三个顶点为 $(1.5, 4.5), (-4, -1), (7, -1)$ 的三角形，这个等腰直角三角形的斜边长度为 11。

在直角顶点位于斜边下方的等腰直角三角形中，斜边最短的是如下图所示的，三个顶点为 $(2, -3), (-5, 4), (9, 4)$ 的三角形，这个等腰直角三角形的斜边长度为 14。

在这两种等腰直角三角形中，斜边较短的是直角顶点位于斜边上方的情况，因此所求的长度为 11。

输入格式

第一行给定一个整数 $N$。

接下来的 $N$ 行中，第 $i$ ($1 \le i \le N$) 行给定两个整数 $x_i$ 和 $y_i$，以空格分隔。

输出格式

在第一行输出满足所有条件的等腰直角三角形中，斜边长度最短的那个的斜边长度。可以证明答案总是一个整数。

3
0 0
2 3
4 0

6

2
0 0
5 2

7

4
1 5
3 2
6 6
7 4

10

提示

样例 1 解释

以 $(-1, 0), (2, 3), (5, 0)$ 为三个顶点的等腰直角三角形满足所有条件，其斜边长度为 6，是最短的。

样例 2 解释

满足所有条件且斜边长度为 7 的等腰直角三角形有如下两种。

• 以 $(0, 0), (7, 0), (3.5, 3.5)$ 为三个顶点的三角形

• 以 $(-2, 2), (5, 2), (1.5, -1.5)$ 为三个顶点的三角形

限制条件

• 给定的所有数都是整数。
• $2 \le N \le 100,000$。
• 对于每个 $1 \le i \le N$ 的 $i$，有 $-100,000,000 \le x_i, y_i \le 100,000,000$。
• 给定的 $N$ 个点都各不相同。也就是说，对于所有 $1 \le i < j \le N$ 的 $i, j$，都有 $x_i \ne x_j$ 或 $y_i \ne y_j$。

子任务

1. (10 分) $N \le 2$。
2. (18 分) $N \le 3$。
3. (20 分) $N \le 50$，且对于每个 $1 \le i \le N$ 的 $i$，有 $-30 \le x_i, y_i \le 30$。
4. (10 分) $N \le 50$。
5. (4 分) 对于每个 $2 \le i \le N$ 的 $i$，有 $y_i = y_{i-1}$。也就是说，所有点的 $y$ 坐标都相同。
6. (6 分) 对于每个 $1 \le i \le N$ 的 $i$，有 $x_i = y_i$。
7. (10 分) 在所有满足给定条件且斜边长度最短的等腰直角三角形中，至少有一个的斜边中点是 $(0, 0)$。
8. (22 分) 无附加限制条件。