CF314D Sereja and Straight Lines

Sereja 在平面上放置了 $n$ 个点。现在，Sereja 想在平面上放置两条相互垂直的直线，使得其中一条直线与 $Ox$ 轴成 $45$ 度角，并且让所有点到这两条直线的最远距离尽可能小。 在本题中，两点 $(x_{1},y_{1})$ 和 $(x_{2},y_{2})$ 之间的距离定义为 $|x_{1}-x_{2}|+|y_{1}-y_{2}|$。点到直线的距离是该点到直线上某个点的最小距离。 请帮助 Sereja，找出点集到最优放置的两条直线的最大距离的最小值。

第一行包含一个整数 $n$，$(1 \leq n \leq 10^{5})$。接下来的 $n$ 行每行包含两个整数 $x_{i},y_{i}$，$(|x_{i}|, |y_{i}| \leq 10^{9})$，表示第 $i$ 个点的坐标。

输出一个实数，表示问题的答案。若你的答案的绝对误差或相对误差不超过 $10^{-6}$，则视为正确。

由 ChatGPT 5 翻译