← 返回题目列表

Codeforces · 314/D

D. Sereja 和直线

中文机器翻译题面 查看原题

Sereja 在平面上放置了 n 个点。现在 Sereja 想要在平面上放置两条直线,以直角相交,使得其中一条直线与 Ox 轴以 45 度角相交,并且点到直线的最大距离最小。

在这个问题中,我们认为点 (x1, y1) 和 (x2, y2) 之间的距离等于 |x1 - x2| + |y1 - y2|。该点与直线之间的距离是该点到属于其中一条直线的某个点的最小距离。

帮助 Sereja,找到从这些点到最佳位置直线的最大距离。

输入

第一行包含整数 n (1 ≤ n ≤ 105)。接下来的 n 行包含各行的坐标。第 i 行包含两个整数 xi, yi (|xi|, |yi| ≤ 109)。

输出

在一行中打印一个实数——问题的答案。当且仅当其绝对或相对误差不超过 10 - 6 时,您的答案将被视为正确。

示例

输入 #1

4
0 0
2 0
0 2
2 2

输出 #1

0.000000000000000

输入 #2

4
1 0
0 1
2 1
1 2

输出 #2

1.000000000000000