#P5199. Visible Mountain Peaks

    ID: 18435 Type: Default 1000ms 256MiB

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