题目描述

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

---

样例 1

输入

3
5 -3
7 6
4 -4

输出

5.5

解释
字节扎尔可先以每小时 $\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}$ 的距离，且无法更大。

---

样例 2

见附加文件下 met1ocen.in 和 met1ocen.out。
该样例满足 $n=5$, $t_{i}=i$, $x_{i}=2i-6$，答案为 $1 \frac{1}{2}$。

---

样例 3

见附加文件下 met2ocen.in 和 met2ocen.out。
该样例满足 $n=10$, $t_{i}=100$, $x_{i}=(-1)^{i} \cdot i^{2}$，答案为 $19$。

---

样例 4

见附加文件下 met3ocen.in 和 met3ocen.out。
该样例满足 $n=1000$, $t_{i}=4000$, $x_{i}=8i-4004$，答案为 $4$。

---

样例 5

见附加文件下 met4ocen.in 和 met4ocen.out。
该样例满足 $n=200000$, $t_{i}=5000i$, $x_{i}=100000$，答案为 $105000$。

---

数据范围与提示

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

子任务编号	附加限制	分值
1	$t_{i} \leq 1000$ 对所有 $i$	20
2	所有 $t_{i}$ 相等	10
3	$n \leq 1000$	20
4	无附加限制	50