COCI 2020/2021 - Contest 5 - Planine

View as PDF

Submit solution

Points: 1.50 (partial)
Time limit: 2.0s
Memory limit: 512M
Input: stdin
Output: stdout

Suggester:
Problem source:
COCI 2020/2021 - Contest 5
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Chàng trai Zoran đang lang thang quanh quê nhà Dalmatia của anh ấy, cố gắng quên đi nỗi lòng. Zoran đi ngang qua một ngọn núi với một hình dạng khá đặc biệt, mà đằng sau là một thiếu nữ đang đợi chờ anh. Ngọn núi có thể được miêu tả bằng ~n~ đỉnh cao và thấp xen kẽ nhau, với ~n~ lẻ. Các đỉnh ở vị trí lẻ, ngoại trừ đỉnh ở vị trí đầu tiên và vị trí cuối cùng, được gọi là các thung lũng.

Khổ nỗi rằng anh chàng Zoran lại rất sợ bóng tối. Kể cả tiếng gọi của tình yêu cũng không cho anh đủ dũng khí để vượt qua ngọn núi này vào buổi đêm. Như thường lệ, những cô tiên xứ Velebit đã đến để giúp đỡ anh.

Chúng ta sẽ biểu diễn mỗi cô tiên bằng một chấm sáng chói lọi ở một độ cao ~h~ không đổi. Một cô tiên sẽ chiếu sáng một thung lũng khi và chỉ khi đoạn thẳng nối giữa cô tiên và thung lũng không giao với bên trong ngọn núi (xem hình vẽ dưới đây để rõ hơn).

img

Ngọn núi trong test mẫu 1, với một cô tiên chiếu sáng cả ba thung lũng.

Hãy giúp anh chàng Zoran xác định số cô tiên tối thiểu cần để chiếu sáng mọi thung lũng trong cùng một thời điểm.

Input

Dòng đầu tiên chứa hai số nguyên ~n\,(3 \le n < 10^6,\, n~ lẻ~)~ và ~h\,(1 \le h \le 10^6)~, chỉ số đỉnh của ngọn núi và độ cao mà các cô tiên đứng ở.

~n~ dòng tiếp theo, dòng thứ ~i~ chứa các số nguyên ~x_i~ và ~y_i~ ~(-10^6 \le x_i \le 10^6, 0 \le y_i < h)~, là tọa độ đỉnh thứ ~i~ của ngọn núi.

Dữ liệu đầu vào đảm bảo thỏa mãn ~x_1 < x_2 < \ldots < x_n~ và ~y_1 < y_2,\, y_2 > y_3,\, y_3 < y_4, \ldots,\, y_{n - 1} > y_n~.

Output

In ra số cô tiên ít nhất để tất cả các thung lũng được chiếu sáng cùng một thời điểm.

Sample 1

Input
9 6
0 0
1 2
3 0
6 3
8 1
9 2
11 1
12 4
14 0
Output
1
Giải thích

Test mẫu 1 là hình vẽ trong đề.

Sample 2

Input
9 5
-5 2
-4 3
-2 1
0 4
2 2
3 3
4 1
5 2
6 1
Output
2
Giải thích

Có thể thấy rằng, các thung lũng trong ví dụ thứ hai không thể được chiếu sáng bằng chỉ một cô tiên. Một ví dụ sử dụng hai cô tiên có thể thấy trong hình vẽ dưới đây.

img

Ràng buộc

  • ~9~ test đầu tiên thỏa mãn ~y_2 = y_4 = \ldots = y_{n - 1}~.
  • ~7~ test tiếp theo thỏa mãn ~3 \le n < 2000~.
  • ~11~ test còn lại không có thêm ràng buộc gì.

Comments

Please read the guidelines before commenting.


There are no comments at the moment.