L3-009 烽火台选址：几何视角下的最少建造策略

1. 烽火台选址问题的几何本质

想象你是一位古代军事指挥官，负责在长城沿线布置烽火台。每个烽火台需要监控北方区域，但建造太多会浪费资源，太少又会有监控盲区。这本质上是一个几何覆盖问题——如何用最少的点覆盖整个区域。

这个问题和计算几何中的凸包概念密切相关。我们可以把长城看作由一系列顶点组成的折线，烽火台只能建在这些顶点上。关键观察点是：只有当某个顶点是"凸点"时，才需要在此建造烽火台。这里的凸点指的是从该点看北方时，视线不会被相邻的点阻挡。

举个例子，假设有三个连续的点A、B、C。如果B位于AC连线下方（形成凹陷），那么从A就能直接看到C，不需要在B建烽火台；但如果B位于AC连线上方（形成凸起），就必须在B建台，否则A看不到C后面的区域。

2. 斜率比较法的核心原理

判断凸点的关键工具是斜率比较。给定三个连续的点p1、p2、p3，我们可以计算两条线段的斜率：

• p1到p2的斜率k1 = (y2-y1)/(x2-x1)
• p2到p3的斜率k2 = (y3-y2)/(x3-x2)

核心规则：如果k1 ≥ k2，说明p2是一个凹点（不需要建台）；如果k1 < k2，则p2是凸点（需要建台）。这个判断基于几何直观：斜率增大意味着视线被阻挡。

在实际编程实现时，为了避免浮点数精度问题，我们通常将斜率比较转化为交叉相乘： (y2-y1)(x3-x2) ≥ (y3-y2)(x2-x1)

3. 算法实现与优化

这个问题可以用单调栈高效解决。基本思路是维护一个栈，按顺序处理每个点，保持栈中点的斜率单调递增。具体步骤：

1. 初始化空栈
2. 按从南到北顺序遍历每个点
3. 对于当前点，检查栈顶两点和当前点是否满足凸性
4. 如果不满足，弹出栈顶点（说明它是凹点）
5. 将当前点压入栈中
6. 最终栈中剩下的点就是需要建造烽火台的位置

#include<bits/stdc++.h> using namespace std; const int N=1e5+10; int a[N],b[N],vis[N],n,tt,st[N],ans; bool check(int l,int mid,int r) { return (b[l]-b[r])*(a[mid]-a[l]) >= (b[mid]-b[l])*(a[l]-a[r]); } int main() { cin>>n; for(int i=0;i<n;i++) cin>>a[i]>>b[i]; for(int i=0;i<n;i++) { while(tt>1 && check(i,st[tt],st[tt-1])) tt--; if(tt>1 && !vis[st[tt]]) { vis[st[tt]]=1; ans++; } st[++tt]=i; } cout<<ans; return 0; }

这个算法的时间复杂度是O(n)，因为每个点最多进出栈一次。空间复杂度也是O(n)，用于存储输入点和栈。

4. 边界条件与特殊案例

在实际实现时，有几个边界情况需要特别注意：

1. 共线点处理：题目说明与烽火台视线相切的区域也算被监控。这意味着如果三个点共线，中间点不需要建台。我们的斜率比较已经自动处理了这种情况。

2. 输入顺序：题目保证顶点从南到北给出，这简化了我们的处理。如果顺序不确定，需要先排序。

3. 起点处理：最南端的总部不需要考虑建造烽火台，直接从第二个点开始处理。

4. 数值溢出：坐标范围可能很大（到1e9），斜率比较时使用交叉相乘可以避免浮点精度问题，但要注意使用long long防止整数溢出。

5. 实际应用与扩展

虽然这个问题设定在古代军事场景，但类似的算法在现代有很多应用：

1. 无线基站布置：用最少的基站覆盖特定区域
2. 监控摄像头布置：选择最优位置安装摄像头
3. 计算机图形学：可见性计算和遮挡剔除
4. 路径规划：寻找关键转折点

这个问题的变种还包括：

• 双向监控（烽火台需要同时监控南北方向）
• 有限视野范围（烽火台只能看到一定距离）
• 三维空间中的监控点布置

6. 调试技巧与常见错误

在实现这个算法时，新手容易犯的几个错误：

1. 栈操作顺序错误：确保先检查并弹出不符合条件的点，再压入新点
2. 下标越界：处理前两个点时栈中元素不足，需要特殊处理
3. 斜率比较方向错误：注意不等式的方向，可以画图验证
4. 输出计数错误：题目要求输出的是需要建造的烽火台数量，不包括总部

调试时可以先用小规模数据测试，比如：

3 0 0 1 1 2 0

这个简单案例只需要在(1,1)建一个烽火台。

另一个有用的测试案例是：

5 0 0 1 2 2 1 3 3 4 0

正确结果应该是2个烽火台（在(1,2)和(3,3)）。

7. 算法可视化理解

为了更直观地理解算法，可以想象用橡皮筋从下方套住所有点。最终橡皮筋接触的点就是需要建造烽火台的位置——这其实就是计算几何中的"下凸包"概念。

对于输入样例：

10 67 32 48 -49 32 53 22 -44 19 22 11 40 10 -65 -1 -23 -3 31 -7 59

算法会找到两个关键凸点，因此输出2。可以画图验证这些点确实能覆盖整个区域。

8. 性能优化实践

对于最大规模的数据（n=1e5），算法需要进一步优化：

1. 输入输出加速：使用更快的IO方法，如关闭同步流

ios::sync_with_stdio(false); cin.tie(0);

2. 内存访问优化：使用原生数组而非STL容器
3. 减少条件判断：合并一些判断条件
4. 循环展开：编译器通常会自动优化

在在线判题系统中，上述实现已经足够高效。在实际工程应用中，还可以考虑并行化处理或使用SIMD指令进一步加速。