Sereja and Straight Lines

题意翻译

给定平面上 $n$ 个点，你需要选择两条直线，使得这 $n$ 个点到这两条直线距离的最大值尽量小。这两条直线要互相垂直，且与 $x$ 轴夹角为 $45^\circ$。 定义两点 $(x_1,y_1),(x_2,y_2)$ 的距离为 $|x_1-x_2| + |y_1 - y_2|$ ，定义点到直线的距离为点到直线上距离最短的点的距离，点到两条直线的距离即到距离最短直线的距离。 $n \le 10^5,|x_i|,|y_i| \le 10^9$

题目描述

Sereja placed $ n $ points on a plane. Now Sereja wants to place on the plane two straight lines, intersecting at a right angle, so that one of the straight lines intersect the $ Ox $ axis at an angle of $ 45 $ degrees and the maximum distance from the points to the straight lines were minimum. In this problem we consider the distance between points $ (x_{1},y_{1}) $ and $ (x_{2},y_{2}) $ equal $ |x_{1}-x_{2}|+|y_{1}-y_{2}| $ . The distance between the point and the straight lines is the minimum distance from the point to some point belonging to one of the lines. Help Sereja, find the maximum distance from the points to the optimally located straight lines.

输入输出格式

输入格式

The first line contains integer $ n $ $ (1<=n<=10^{5}) $ . Next $ n $ lines contain the coordinates of the lines. The $ i $ -th line contains two integers $ x_{i},y_{i} $ $ (|x_{i}|,|y_{i}|<=10^{9}) $ .

输出格式

In a single line print a real number — the answer to the problem. Your answer will be considered correct iff its absolute or relative error doesn't exceed $ 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