[AdditionalFile3466.zip](file://AdditionalFile3466.zip?type=additional_file)

#3466. 「COCI 2021.2」Planine

标签: 传统 | 时间限制: 2000 ms | 内存限制: 512 MiB |

题目描述

译自 COCI 2020/2021 Contest #5 T4「Planine」

定义山为由 $n$（$n$ 是奇数）个点 $(x_i,y_i)$ 以及 $(x_1,-\inf)$，$(x_n,-\inf)$ 组成的多边形。

定义山谷是这 $n$ 个点中的 $(x_i,y_i)$，要求 $i\not=1,i\not=n,i\equiv1\pmod2$。

现您想在 $y=h$ 这条直线上放上一些点光源，使得所有的山谷都被照亮，照亮的条件是，从某个点光源连一条线段到山谷，这条线段不穿过山内部。

鉴于点光源是要钱的，您需要求出最少需要的点光源个数。

输入格式

第一行两个整数 $n,h$。

接下来 $n$ 行，一行两个整数 $(x_i,y_i)$。

输出格式

仅一行一个整数，表示最少需要的点光源个数。

样例 1

输入

9 6
0 0
1 2
3 0
6 3
8 1
9 2
11 1
12 4
14 0

输出

1

样例 2

输入

9 5
-5 2
-4 3
-2 1
0 4
2 2
3 3
4 1
5 2
6 1

输出

2

数据范围与提示

对于所有子任务，有 $3\le n<10^6$，$n\equiv1\pmod2$，$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$，$y_1<y_2,y_2>y_3,y_3<y_4,\ldots,y_{n-1}>y_n$。