题解：[ABC385F] Visible Buildings

在一条数轴上，存在 $N$ 座编号从 $1$ 到 $N$ 的建筑物。建筑物 $i$ 位于坐标 $X_i$，高度为 $H_i$。除了高度以外的其他方向的大小可以忽略不计，以上输入均为正整数。

从坐标为 $x$、高度为 $h$ 的点 $P$ 出发，如果存在建筑物 $i$ 上的某个点 $Q$，使得线段 $PQ$ 不与任何其他建筑物相交，则建筑物 $i$ 被认为是可见的。

现在需要找出在坐标 $0$ 处，无法看到所有建筑物的最大高度。高度必须为非负数；如果在坐标 $0$ 处高度 $0$ 可以看到所有建筑物，那么报告 $-1$。

首先，我们考虑只有两栋建筑物，最高能到多高，仍看不到所有建筑物。如图所示，显然两栋建筑物的顶点连线与 $y$ 轴的交点，就是最高的高度。因为一旦高度更高，我们与第二栋建筑物的连线就不交与任何建筑物，就能看到了。

然后，我们考虑加入第三栋建筑物在中间会如何。

若这栋建筑物在原直线的下面，如图，那么新加入的建筑物与左边的建筑物组合，得到了更高的一条连线，这是新的最高的高度。

若这栋建筑物在原直线的上面，如图，那么新加入的建筑物与右边的建筑物组合，得到了更高的一条连线，这是新的最高的高度。

于是我们得到结论，对于每一栋建筑物，我们只需要考虑与其相邻的建筑物，连线，并找到与 $y$ 轴相交点的最大高度即可。

我们考虑两个点，坐标为 $(x_1,y_1)$，$(x_2,y_2)$。

待定系数，得

解得

将 $x = 0$ 带入，坐标即为 $(0,b)$，此题完结。

输入有 $1 \leq X_1 < X_2 < \cdots < X_N \leq 10^9$，所以无需按 $x$ 排序，且 $x$ 相乘小于 $10^{18}$，不用担心溢出问题。