COCI '20 Contest 5 #4 Planine

View as PDF

Submit solution

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 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.

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

Input Specification

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

The i^\text{th} of the following n lines contains integers x_i and y_i (-10^6 \le x_i \le 10^6, 0 \le y_i < h), the coordinates of the i^\text{th} point of the mountain.

It is guaranteed that x_1 < x_2 < \dots < x_n, and y_1 < y_2, y_2 > y_3, y_3 < y_4, \dots, y_{n-1} > y_n.

Output Specification

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


120y_2 = y_4 = \dots = y_{n-1}
2303 \le n < 2\,000
360No additional constraints.

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


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


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.


There are no comments at the moment.