题解：P11596 [NOISG 2018 Finals] Lightning Rod

· · 题解

1. 题意

有若干座高楼大厦，需要在某一些大楼的顶部安装避雷针。

求最少需要安装多少避雷针，才能保证所有的大楼都在保护范围内。

2. 分析

本题可以看做是一个计算几何问题，属于图形覆盖问题。

根据题意，每根避雷针保护的区域是以该避雷针所在位置为顶点的等腰直角三角形区域。

分析过程中，如果出现了大三角形完全覆盖小三角形的情况，意味着小三角形对应的避雷针是不必要的。

由于题目中保证所有的横坐标单调不减地给出（其实不保证单调不减也无所谓，多一步排序操作就可以了，但就本题而言可能会出现TLE），因此我们可以线性扫描。

我们可以考虑用一个栈维护所有三角形，栈顶的元素是扫描到当前位置，横坐标最靠右的，必须使用的三角形。

当新加入一个三角形时...

判断是否覆盖的本质是比较某点（楼顶）位置 (x_A,y_A) 到另一栋大楼底部 (x_B,0) 的街区距离是否小于另一栋大楼的高度 y_B。

全部扫描完毕后，栈中的三角形数量就是答案。

3. 代码

必须使用快读。使用 scanf 或者 cin 或者 C# 的 StreamReader （据说相当于 C++ 的快读）皆会出现 TLE。

#include <cstdio>
#include <stack>
#include <cmath>
using namespace std;

class TriangleVertex {
public:
    int topX, topY;
    bool TriangleCover(TriangleVertex& another) const noexcept
    {
        return abs(topX - another.topX) <= topY - another.topY;
    }
    TriangleVertex(int x, int y) : topX(x), topY(y) { }
}

inline int readInt() 
{
    int x = 0;
    char ch = getchar_unlocked();
    while (ch < '0' || ch > '9') ch = getchar_unlocked();
    while (ch >= '0' && ch <= '9')
    {
        x = (x << 3) + (x << 1) + ch - '0';
        ch = getchar_unlocked();
    }
    return x;
}

int main(void)
{
    stack<TriangleVertex> triangle_needed;
    int n = readInt(), x, y;
    for (int i = 0; i < n; ++i) 
    {
        x = readInt(), y = readInt();
        TriangleVertex vertex(x, y);
        if (!triangle_needed.empty() && triangle_needed.top().TriangleCover(vertex))
        {
            continue;
        }
        while (!triangle_needed.empty() && vertex.TriangleCover(triangle_needed.top()))
        {
            triangle_needed.pop();
        }
        triangle_needed.push(vertex);
    }
    printf("%d\n", triangle_needed.size());
}

记录：https://www.luogu.com.cn/record/201460012

4. Trivia

本题的情景同样可以推广到三维空间。

如果推广到三维空间，则位于 (x_0,y_0,z_0) 的避雷针可以覆盖的区域是一个以该点为顶点的正四棱锥区域，这个边界区域的方程是 |x-x_0|+|y-y_0|+z=z_0，其中 z,z_0 必须为正，x,y,x_0,y_0 可正可负。使用类似的方法同样可以解决三维问题。

由于题目中，栈中存储的是横坐标最大的，必须使用的三角形；类似的，在三维问题中可以考虑按照距离原点的水平距离 \sqrt{x_0^2+y_0^2} 作为指标，栈顶存储的是距离原点最远的，必须使用的金字塔。

这里假设所有的坐标 (x_i,y_i,z_i) 全为正并且按照 \sqrt{x_i^2+y_i^2} 单调不减输入。

代码：

#include <cstdio>
#include <stack>
#include <cmath>
using namespace std;

class Pyramid {
public:
    int topX, topY, topZ;
    Pyramid(int x, int y, int z) : topX(x), topY(y), topZ(z) {}
    bool PyramidCover(Pyramid& another) const noexcept 
    {
        return abs(topX - another.topX) + abs(topY - another.topY) <= topZ - another.topZ;
    }
};

inline int readInt()
{
    int x = 0;
    char ch = getchar_unlocked();
    while (ch < '0' || ch > '9') ch = getchar_unlocked();
    while (ch >= '0' && ch <= '9')
    {
        x = (x << 3) + (x << 1) + ch - '0';
        ch = getchar_unlocked();
    }
    return x;
}

int main(void)
{
    stack<Pyramid> pyramid_needed;
    int n = readInt(), x, y, z;
    for (int i = 0; i < n; ++i)
    {
        x = readInt(), y = readInt(), z = readInt();
        Pyramid vertex(x, y, z);
        if (!pyramid_needed.empty() && pyramid_needed.top().PyramidCover(vertex))
        {
            continue;
        }
        while (!pyramid_needed.empty() && vertex.PyramidCover(pyramid_needed.top()))
        {
            pyramid_needed.pop();
        }
        pyramid_needed.push(vertex);
    }
    printf("%d\n", pyramid_needed.size());
}