## COCI '20 Contest 5 #4 Planine

View as PDF

Points: 17 (partial)
Time limit: 2.0s
Memory limit: 512M

Problem type

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 alternating low and high points, where 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 . 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.

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

#### Input Specification

The first line contains two integers is odd and , the number of points describing the mountain and the height the fairies live at.

The of the following lines contains integers and , the coordinates of the point of the mountain.

It is guaranteed that , and .

#### Output Specification

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

120
230

#### Sample Input 1

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

#### Sample Output 1

1

#### Explanation for Sample Output 1

The first example is shown in the problem statement.

#### Sample Input 2

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

#### Sample Output 2

2

#### Explanation for Sample Output 2

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 in the figure below.