题目背景

翻译来自于 LibreOJ。

题目描述

题目译自 XXIX Olimpiada Informatyczna – III etap Meteory

字节王国是一个美丽却无限平坦的单维国度，可以看作一条数轴。很快，这里将迎来一场流星雨。根据字节王国气象学家的精准预测，会有正好 $n$ 颗流星坠落。更妙的是，他们还准确知道了每颗流星坠落的时间和地点：第 $i$ 颗流星将在 $t_{i}$ 小时落在位置 $x_{i}$。

现在是 $0$ 时刻，Bajtazar 位于位置 $0$。因为流星很危险，而他随身携带的笔记本电脑里存着重要数据，他非常害怕数据受损，所以想尽量远离任何流星。具体来说，他希望最大化自己与最近坠落流星的距离（每次距离在流星坠落时测量）。

假设 Bajtazar 跑步速度最多为每小时 $1$ 个单位（可向左或向右），且永不疲倦。他还能瞬间多次转向。请你帮助 Bajtazar 保护自己和他的数据，编写一个程序，读取流星信息，计算他能与最近的流星保持的最大距离。

输入格式

输入的第一行包含一个整数 $n$ $(1 \leq n \leq 200000)$，表示流星数量。接下来的 $n$ 行每行描述一颗流星，包含两个整数 $t_{i}$ 和 $x_{i}$ $(0 \leq t_{i} \leq 10^{9}, -10^{9} \leq x_{i} \leq 10^{9})$，分别表示第 $i$ 颗流星坠落的时间和位置。

输出格式

输出一行，包含一个实数，精确到小数点后一位，表示字节扎尔在最优策略下与最近流星的最大距离。若结果为整数，可带一位小数 $0$（如 $5.0$）或不带小数点（如 $5$）。

3
5 -3
7 6
4 -4

5.5

提示

样例 1 解释

字节扎尔可先以每小时 $\frac{1}{2}$ 的速度向右跑，到第 $4$ 小时到达位置 $2$（距第 $3$ 颗流星 $6$ 单位），第 $5$ 小时到达 $2 \frac{1}{2}$（距第 $1$ 颗流星 $5 \frac{1}{2}$ 单位）。然后他需转向，以最大速度 $1$ 向左跑，到第 $7$ 小时到达 $\frac{1}{2}$（距第 $2$ 颗流星 $5 \frac{1}{2}$ 单位）。这样，他始终与最近流星保持至少 $5 \frac{1}{2}$ 的距离，且无法更大。

附加样例

1. 该样例满足 $n=5, t_{i}=i, x_{i}=2i-6$，答案为 $1 \frac{1}{2}$；
2. 该样例满足 $n=10, t_{i}=100, x_{i}=(-1)^{i} \cdot i^{2}$，答案为 $19$；
3. 该样例满足 $n=1000, t_{i}=4000, x_{i}=8i-4004$，答案为 $4$；
4. 该样例满足 $n=200000, t_{i}=5000i, x_{i}=100000$，答案为 $105000$。

详细子任务附加限制及分值如下表所示。