| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2.5 초 | 512 MB | 46 | 10 | 9 | 33.333% |
Singapore has anywhere between 171 and 186 lightning days on average a year. Each square kilometer of land in Singapore can be struck up to 16 times annually. This makes Singapore one of the lightning capitals of the world.
Gug the architect surveys N buildings from left to right, and notices that the top of building i, from left to right, has coordinates (Xi, Yi). Gug wants to protect all the buildings by planting lightning rods on top of some buildings. A lightning rod protects the building it is planted on, and all buildings that lie on or under the 45◦ line of depression leftwards and rightwards. In other words, a lightning rod on building i protects building j if and only if |Xi − Xj| ≤ Yi − Yj.
Help Gug find out the minimum number of lightning rods required to protect all buildings.
Your program must read from standard input.
The input starts with a single integer, N, in a single line. N denotes the total number of buildings.
N lines will then follow with 2 integers each, the ith line will contain Xi and Yi. This indicates that the peak of the ith building is at (Xi, Yi). You can assume Xi ≤ Xi+1, in other words, Xi is increasing.
Note: The input size is extremely large, so it is only possible to obtain full credit using C++ fast input. The submit page consists of a template that uses C++ fast input to read from standard input.
Your program must print to standard output.
Output a single integer, denoting the minimum number of lightning rods required to protect all buildings.
2 1 1 2 1
2
Both buildings must have lightning rods.
2 1 0 2 1
1
A lightning rod can be planted on building 2.
4 1 1 3 2 4 3 5 1
2
Figure 3: Sample 3, where Gug sees 4 buildings.
Lightning rods can be planted on buildings 1 and 3 (see Figure 3).
C++17, C++14, C++20, C++14 (Clang), C++17 (Clang), C++20 (Clang)