题解：[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)。

待定系数，得

k x_1 + b = y_1\\ k x_2 + b = y_2\\ \end{cases}

解得

b = \frac{ x_1 y_2 - x_2 y_1 } {x_1-x_2}

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

细节

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