P12922 [POI 2021/2022 R3] 流星 / Meteory

翻译来自于 [LibreOJ](https://loj.ac/p/4859)。

**题目译自 [XXIX Olimpiada Informatyczna – III etap](https://sio2.mimuw.edu.pl/c/oi29-3/dashboard/) [Meteory](https://szkopul.edu.pl/problemset/problem/k6tz-HdwVKUeP7p9RMpRE6RO/statement/)** 字节王国是一个美丽却无限平坦的单维国度，可以看作一条数轴。很快，这里将迎来一场流星雨。根据字节王国气象学家的精准预测，会有正好 $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 解释** 字节扎尔可先以每小时 $\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$。 详细子任务附加限制及分值如下表所示。 | 子任务编号 | 附加限制 | 分值 | | :---: | :--: | :---: | | $1$ | $t_{i} \leq 1000$ 对所有 $i$ | $20$ | | $2$ | 所有 $t_{i}$ 相等 | $10$ | | $3$ | $n \leq 1000$ | $20$ | | $4$ | 无附加限制 | $50$ |