题目描述

题目译自 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

样例 2

见附加文件下 [met1ocen.in](file:met1ocen.in) 和 [met1ocen.out](file:met1ocen.out)。

该样例满足 $n=5, t_{i}=i, x_{i}=2i-6$，答案为 $1 \frac{1}{2}$；

样例 3

见附加文件下 [met2ocen.in](file:met2ocen.in) 和 [met2ocen.out](file:met2ocen.out)。

该样例满足 $n=10, t_{i}=100, x_{i}=(-1)^{i} \cdot i^{2}$，答案为 $19$；

样例 4

见附加文件下 [met3ocen.in](file:met3ocen.in) 和 [met3ocen.out](file:met3ocen.out)。

该样例满足 $n=1000, t_{i}=4000, x_{i}=8i-4004$，答案为 $4$；

样例 5

见附加文件下 [met4ocen.in](file:met4ocen.in) 和 [met4ocen.out](file:met4ocen.out)。

该样例满足 $n=200000, t_{i}=5000i, x_{i}=100000$，答案为 $105000$。

数据范围与提示

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