#P5199. Visible Mountain Peaks
Visible Mountain Peaks
Visible Mountain Peaks
Bessie the cow is looking into the distance from her pasture and sees a line of mountains. In her view, the mountains are represented as isosceles right triangles with their bases on the x-axis. The peak of mountain i is given by coordinates \( (x_i,y_i) \). Each mountain forms a triangle whose sides make a \(45^\circ\) angle with the base. This implies that the mountain's triangle covers all points \( (x,y) \) satisfying:
[ y \le y_i - |x - x_i| ]
A mountain peak is hidden if it lies in or on the boundary of the triangle formed by another mountain. In other words, mountain j's peak \( (x_j,y_j) \) is hidden by mountain i if:
[ y_j \le y_i - |x_j - x_i| ]
Your task is to determine how many mountain peaks are visible to Bessie.
inputFormat
The first line contains an integer \(N\) (\(1 \le N \le 10^5\)), the number of mountains. Each of the next \(N\) lines contains two space-separated integers \(x_i\) and \(y_i\), representing the coordinates of the peak of the \(i\)-th mountain.
outputFormat
Output a single integer representing the number of visible mountain peaks.
sample
5
4 5
5 3
8 4
8 10
3 7
2