题意简述

输入一个由 $n$ 个点（$n$ 为奇数）组成的多边形，表示一座“山”。

山谷是位于奇数下标（1-based）且不是第一个和最后一个的点，即 $i=3,5,7,\dots,n-2$ 且 $i$ 为奇数。

在直线 $y=h$ 上放置点光源，要求每个山谷与至少一个点光源的连线不穿过山体内部。

求最少需要多少个点光源。

关键观察

山谷位置 因为 $y_1<y_2>y_3<y_4>y_5<\dots$，所以山谷是纵坐标的局部极小点（除了首尾），即 $y_3, y_5, y_7, \dots$。

照亮条件 从点光源 $(X, h)$ 到山谷 $(x_i, y_i)$ 的线段不能与山体内部相交。 山体由连续折线构成，因此该线段不能与任何非相邻的山体边相交。

几何转化 对于某个山谷 $P_i=(x_i,y_i)$，能照亮它的点光源 $(X,h)$ 必须满足：

从 $P_i$ 向左右两侧的“山脊”连线，与直线 $y=h$ 相交，得到一个区间 $[L_i,R_i]$，表示能照亮此山谷的 $X$ 坐标范围。

这个区间可以通过从 $P_i$ 向左和向右作射线，与 $y=h$ 相交得到。 向左时，射线不能越过左边相邻的顶点；向右时，不能越过右边相邻的顶点。 实际上，由于山形是连续的相邻点交替上下，所以向左的射线会碰到左侧的“山脊”边，向右同理。

区间推导

设山谷 $P_i=(x_i,y_i)$。

向左：连接 $P_i$ 与左侧第一个比它高的顶点 $P_{i-1}$，延长到 $y=h$，得到左边界 $L_i$。

向右：连接 $P_i$ 与右侧第一个比它高的顶点 $P_{i+1}$，延长到 $y=h$，得到右边界 $R_i$。

推导公式（相似三角形）：

L i

x i − ( h − y i ) ( x i − x i − 1 ) y i − 1 − y i L i ​ =x i ​ − y i−1 ​ −y i ​

(h−y i ​ )(x i ​ −x i−1 ​ ) ​

R i

x i + ( h − y i ) ( x i + 1 − x i ) y i + 1 − y i R i ​ =x i ​ + y i+1 ​ −y i ​

(h−y i ​ )(x i+1 ​ −x i ​ ) ​

注意：因为 $y_{i-1} > y_i$ 且 $y_{i+1} > y_i$，分母为正。

问题转化

每个山谷对应一个区间 $[L_i, R_i]$，我们要在 $y=h$ 上选最少的点，使得每个区间至少包含一个点。

这就是经典的区间覆盖问题（点覆盖区间）： 给定若干区间，求最少需要多少个点，使得每个区间至少包含一个点。

贪心解法：

按 $R_i$ 排序。

遍历区间，如果当前区间不包含已选的点，则在该区间的右端点放一个点。

算法步骤

找出所有山谷位置 $i=3,5,\dots,n-2$。

对每个山谷计算 $[L_i, R_i]$。

按 $R_i$ 排序。

贪心选择点。

时间复杂度

计算区间 $O(n)$

排序 $O(n \log n)$

贪心 $O(n)$ 总 $O(n \log n)$，可过 $n \le 10^6$。

示例代码（框架）

cpp #include <bits/stdc++.h> using namespace std;

struct Interval { double L, R; bool operator<(const Interval& other) const { return R < other.R; } };

int main() { int n, h; scanf("%d%d", &n, &h); vector x(n), y(n); for (int i = 0; i < n; i++) { scanf("%lf%lf", &x[i], &y[i]); }

vector<Interval> intervals;
for (int i = 2; i < n - 1; i += 2) { // 山谷下标（0-based）：2,4,6,...,n-3
    double L = x[i] - (h - y[i]) * (x[i] - x[i-1]) / (y[i-1] - y[i]);
    double R = x[i] + (h - y[i]) * (x[i+1] - x[i]) / (y[i+1] - y[i]);
    intervals.push_back({L, R});
}

sort(intervals.begin(), intervals.end());

int ans = 0;
double last = -1e18;
for (auto& inv : intervals) {
    if (inv.L > last) {
        ans++;
        last = inv.R;
    }
}

printf("%d\n", ans);
return 0;

}

总结

本题核心是将照亮条件转化为区间覆盖问题：

确定每个山谷的可见光源区间。

贪心求解最少的点覆盖所有区间。