P5199 [USACO19JAN] Mountain View S

USACO January 2019 Contest, Silver Problem 3.

Looking into the distance from the pasture of the cow Bessie, she can see a magnificent mountain range stretching along the horizon. The range contains $N$ mountain peaks ($1 \le N \le 10^5$). If we imagine Bessie’s view as the $xy$-plane, then each mountain is a triangle whose base lies on the $x$-axis. Both sides of the triangle make a $45$ degree angle with the base, so the вершина (pinnacle, "fengding") is a right angle. Therefore, mountain $i$ can be described exactly by the coordinates of its peak $(x_i, y_i)$. No two mountains have exactly the same peak coordinates. Bessie tries to count all the mountains. However, because they are almost the same color, if the peak of one mountain lies on the boundary or inside the triangular region of another mountain, she cannot distinguish it. Find the number of distinct mountain peaks that Bessie can see, i.e. the number of visible mountains.

The first line contains $N$. The next $N$ lines each contain $x_i$ ($0 \le x_i \le 10^9$) and $y_i$ ($1 \le y_i \le 10^9$), describing the coordinates of a mountain’s peak.

Output the number of mountains that Bessie can distinguish.

In this example, Bessie can see the first and the last mountains. The second mountain is covered by the first mountain. Translated by ChatGPT 5