K - ターゲット
Editorial
/
円の列 C_1, C_2, ..., C_K は各 i に対し C_{i+1} が C_i の strictly に内部にあるときサイズ K のターゲットであるという。
すぬけ君は、円を N 個描いた。i 番目の円は中心が (x_i, 0) であり、半径が r_i である。この中から円をいくつか選んでターゲットを作るとき、ターゲットの最大サイズを求めよ。
入力は以下の形式で標準入力から与えられる。
答えを一行に出力せよ。
C_1 を二番目の円、C_2 を一番目の円とすればよい。
円の包含関係は strict である (境界が重なっている場合は内部とはみなさない)。
Time Limit: 2 sec / Memory Limit: 256 MB
Problem Statement
Constraints
- 1 ≤ N ≤ 100000
- 0 ≤ x_i ≤ 100,000,000
- 1 ≤ r_i ≤ 100,000,000
Input Format
N x_1 r_1 … x_N r_N
Output Format
Sample Input 1
3 1 1 0 3 3 2
Sample Output 1
2
Sample Input 2
2 1 1 2 2
Sample Output 2
1