分数: 525 点
问题陈述
有 N 建筑物编号
数轴上的 1 to N 。
大楼 i 位于坐标处 X_i 并且具有高度 H_i。除高度外的其他方向的尺寸可以忽略不计。
从一点 P 坐标 x 和高度 h,建筑 如果存在一个点,则 i 被视为可见 Q 关于建筑 i 使得线段 PQ 不与任何其他建筑物相交。
找到坐标处的最大高度 0 从中不可能看到所有建筑物。高度必须为非负值;是否可以在高处看到所有建筑物 0 在坐标处 0,报告 -1 代替。
约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq X_1 < \dots < X_N \leq 10^9
- 1 \leq H_i \leq 10^9
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N X_1 H_1 \vdots X_N H_N
输出
如果可以从坐标看到所有建筑物 0 和高度 0,打印 -1。否则,打印坐标处的最大高度 0 从中不可能看到所有建筑物。答案的绝对或相对误差最多为 10^{-9} 真实答案将被视为正确。
样本输入 1
3 3 2 5 4 7 5
示例输出 1
1.500000000000000000
从坐标 无法看到 0 和高度 1.5,建筑 如果存在一个点,则 3 。如果高度稍微大于 1.5,所有建筑物,包括建筑物 可以看到 3 。因此,答案是 1.5.

示例输入 2
2 1 1 2 100
示例输出 2
-1
请注意 -1.000 或类似的输出将被视为不正确。
示例输入 3
3 1 1 2 2 3 3
示例输出 3
0.000000000000000000
示例输入 4
4 10 10 17 5 20 100 27 270
示例输出 4
17.142857142857142350