Peter_Matthew的博客

题解 GPLT L3-009 长城

2025-08-06

本文共586字，大约需要阅读2分钟。

从南到北的折线中，选取尽量少的点建造烽火台，使得敌情可以通过北向南传递到总部，且每一个敌情点能被北方某个烽火台“看到”（没有遮挡）。

设点 A、B、C 从南到北排列,如果你从 C 看向 A，但中间的 B 挡住了视线（因为 B 比连线 AC 更高），那么就说明C → A 不可见，因为 B 遮挡。这个几何问题，本质上就是三点是否形成“凹形”或“右转”。

判断三点 A, B, C 是否构成凹形 —— 用 叉积（cross product）判断转向方向：
叉积公式：
$$ (p2 - p1) \times (p3 - p2) = (x2 - x1) \ast (y3 - y2) - (y2 - y1) \ast (x3 - x2) $$
如果结果 ≥ 0：说明是右转或共线（遮挡）

整体做法是：

  1. 初始化栈为空。
  2. 从第一个点（最南端，总部）开始，依次处理每个点。
  3. 对于当前点，如果前面两个栈顶点 + 当前点构成凹形（即中间点会遮挡），就把中间点从栈中弹出。然后判断栈顶点是否已经是烽火台：如果不是，则现在它必须成为烽火台。
  4. 最后把当前点压入栈。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<bits/stdc++.h>
using namespace std;

// 判断是否形成“右转”或“共线”（即中间点被遮挡）
bool isConcave(int l, int mid, int r, const vector<long long>& X, const vector<long long>& Y) {
    return (Y[r] - Y[l]) * (X[mid] - X[l]) >= (Y[mid] - Y[l]) * (X[r] - X[l]);
}

int main() {
    int n;
    cin >> n;

    vector<long long> X(n), Y(n);
    for (int i = 0; i < n; ++i) {
        cin >> X[i] >> Y[i];
    }

    vector<int> tower;       // 单调栈：用于维护可见性链上的点下标
    vector<bool> vis(n, false); // 标记哪些点被选为烽火台
    int ans = 0;

    for (int i = 0; i < n; ++i) {
        if (!tower.empty()) {
            // 如果形成了“凹形”（右转），弹出中间的那个点
            while (tower.size() > 1 && isConcave(i, tower.back(), tower[tower.size() - 2], X, Y)) {
                tower.pop_back();
            }
            // 如果当前 tower 栈顶的点未被标记为烽火台，则现在它必须成为一个烽火台
            if (tower.size() != 1 && !vis[tower.back()]) {
                vis[tower.back()] = true;
                ++ans;
            }
        }
        tower.push_back(i);  // 当前点加入栈（作为可能的烽火台或可见链上的一员）
    }

    cout << ans << endl;
    return 0;
}
当前页共有次阅读，条评论。
标签: 题解
← 题解 GPLT L2-025 分而治之
赏
使用支付宝打赏
使用微信打赏

若你觉得我的文章对你有帮助，欢迎点击上方按钮对我打赏