P7401 [COCI 2020/2021 #5] Planine

There is a mountain with ups and downs. It can be modeled as a polygon consisting of $n$ points $(x_i, y_i)$ (where $n$ is odd), plus the two points $(x_1, -\inf)$ and $(x_n, -\inf)$. For every integer $i$ satisfying $i \neq 1$, $i \neq n$, and $i \bmod 2 = 1$, the point $(x_i, y_i)$ is a valley. Now we want to place some point light sources at height $h$, so that all valleys are illuminated, meaning the line segment connecting a light source and a valley does not pass through the interior of the mountain. Find the minimum number of light sources needed.

The first line contains integers $n, h$. The next $n$ lines each contain integers $x_i, y_i$. It is guaranteed that $x_1 < x_2 < \cdots < x_n$ and $y_1 < y_2, y_2 > y_3, y_3 < y_4, \cdots, y_{n-1} > y_n$.

Output the minimum number of light sources needed.

#### Illustration for Sample 1  #### Illustration for Sample 2  #### Constraints **This problem uses bundled testdata**. | Subtask | Score | Constraints and Notes | | :----------: | :----------: | :----------: | | $1$ | $20$ | $y_2 = y_4 = \cdots = y_{n-1}$ | | $2$ | $30$ | $3 \le n < 2000$ | | $3$ | $60$ | None | For $100\%$ of the testdata: $3 \le n < 10^6$, $n \bmod 2 = 1$, $1 \le h \le 10^6$, $-10^6 \le x_i \le 10^6$, $0 \le y_i < h$, $x_1 < x_2 < \cdots < x_n$, and $y_1 < y_2, y_2 > y_3, y_3 < y_4, \cdots, y_{n-1} > y_n$. #### Notes **The scoring of this problem follows the original COCI problem, with a full score of $110$.** **Translated from [COCI2020-2021](https://hsin.hr/coci/archive/2020_2021/) [CONTEST #5](https://hsin.hr/coci/archive/2020_2021/contest5_tasks.pdf) _T4 Planine_.** Translated by ChatGPT 5