← 返回题目列表

AtCoder · abc385_f

I. 可见建筑物

中文机器翻译题面 查看原题

分数: 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.

Figure


示例输入 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