题解：[ABC385F] Visible Buildings

· · 题解

看起来很难，实际上是一道简单的初中数学题。学过一次函数（雾）的都应该会做。

注意点：初二（好像是）学的一次函数 y = kx + b 的 k 其实就是斜率，只是在初中老师一般没有指明 k 是斜率，b 是 y 轴上的截距而已。

赛时分析（有改动）

题目告诉我们，一个位置 (X_i, H_i) 的建筑从 (0, h) 可见，当且仅当从 (0, h) 到建筑 i 的视线不会被其他建筑阻挡。

不妨用数学语言表达：建筑 i 可见的条件是，从 (0, h) 到 (X_i, H_i) 的斜率大于从 (0, h) 到所有前面建筑的斜率。

学过一次函数的都知道，(0, h) 到 (X_i, H_i) 的斜率公式为：

\text{slope}_i = \frac{H_i - h}{X_i}

我们说建筑 i 是可见的，当且仅当：

\frac{H_i - h}{X_i} > \max_{j < i} \left( \frac{H_j - h}{X_j} \right)

也就是说：

h > \frac{H_j X_i - H_i X_j}{X_i - X_j}

对于所有 j < i 都需要满足。

因此，为了使所有建筑物可见，h 必须大于上述公式中最大值。不难发现，h 的最大值是由两个相邻的建筑 (i-1, i) 决定的。因此只需考虑相邻建筑即可，将时间复杂度优化为 O(N)。

我们来模拟一下第一个样例。

$i = 3$ 时，$h_{3} = \frac{4 \times 7 - 5 \times 5}{7 - 5} = \frac{28 - 25}{2} = 1.5

所以，最大值 min\{h_i\} = 1.5。

赛时代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n;
double maxh = - 1e18;
pair <int, int> h[200010];
signed main() {
    ios :: sync_with_stdio(false);
    cin . tie(nullptr);
    cin >> n;
    for (int i = 1; i <= n; i ++) cin >> h[i] . first >> h[i] . second; // 输入
    for (int i = 2; i <= n; i ++) {
        // 注意需要从第二个开始，因为取的是相邻的
        int X_1 = h[i] . first, H_1 = h[i] . second; 
        int X_2 = h[i - 1] . first, H_2 = h[i - 1] . second;
        // 这里分别表示出相邻的两栋楼
        maxh = max(maxh, (double)(H_2 * X_1 - H_1 * X_2) / (double)(X_1 - X_2));
        // 求斜率并取最大值
    }
    if (maxh < 0) cout << "-1" << endl;
    // 无解
    else cout << fixed << setprecision(12) << maxh << endl;
    // 输出结果
    return 0;
}

完结撒花，记得点赞 [嘿嘿]。