#K7601. Maximum Communication Towers
Maximum Communication Towers
Maximum Communication Towers
You are given n towers on a one-dimensional line. Each tower is described by two integers: its position x and its signal range r. The signal of a tower covers the interval \( [x - r,\; x + r] \). Two towers can communicate with each other if the right endpoint of one tower's range is no less than the left endpoint of the other tower's range.
Your task is to select a subset of towers such that for any two consecutive towers in your chosen order (after sorting by position), the following condition holds:
\( x_j + r_j \ge x_i - r_i \) for any tower \( j \) chosen before tower \( i \).
Determine the maximum number of towers that can simultaneously communicate with each other.
Note: The input is given through stdin
and the output should be printed to stdout
.
inputFormat
The first line contains an integer \( n \) representing the number of towers.
Each of the following \( n \) lines contains two integers \( x \) and \( r \) separated by a space, indicating the position and signal range of a tower, respectively.
\( 1 \le n \le 10^5 \) (for the given problem size, a quadratic algorithm is acceptable for small \( n \)).
outputFormat
Output a single integer representing the maximum number of towers that can communicate with each other.
## sample4
1 2
2 1
5 1
10 2
2