20962번 - Planine 서브태스크다국어

Zoran wanders across his Dalmatian homeland to forget his love woes. He came across a mountain of a specific shape, behind which a young maiden is waiting for him. The mountain can be described with n alternating low and high points, where n is odd. Points at odd indices, except the first and the last point, are called valleys.

Zoran is afraid of the dark. Even the call of love will not give him courage to cross the mountain at night. As usual, the fairies of Velebit come to the rescue.

We model each fairy by a luminous dot at a fixed height h. A fairy illuminates the valley if and only if the segment connecting the fairy and the valley does not intersect the interior of the mountain.

The mountain from the first example, and a fairy illuminating all three valleys.

What is the least number of fairies which can illuminate all the valleys simulaneously?

The first line contains two integers n (3 ≤ n < 10⁶, n odd) and h (1 ≤ h ≤ 10⁶), the number of points describing the mountain and the height the fairies live at.

The i-th of the following n lines contains integers x_i and y_i (−10⁶ ≤ x_i ≤ 10⁶, 0 ≤ y_i < h), the coordinates of the i-th point of the mountain.

It is guaranteed that x₁ < x₂ < · · · < x_n, and y₁ < y₂, y₂ > y₃, y₃ < y₄, . . ., y_n−1 > y_n.

Output the least number of fairies such that all valleys are illuminated.

The first example is shown in the statement. It can be shown that the valleys in the second example cannot be illuminated using only one fairy. An example with two fairies is given on the figure below.