Programming contests

DEIK Regionális Programozó Csapatverseny, középiskolai kategória, 2022. december 4.

December 4, 2022 10:00 AM – December 4, 2022 3:15 PM

domino

Dominos with different heights (x1,h1),...,(xN,hN) are standing on the x-axis. Every domino stands in a way that its base is perpendicular to the axis and the axis goes through the center of its base. The x coordinate and the height of the k-th domino are xk and hk (k=1...N) respectively. No two dominos have the same x coordinate. Pushing the domino (xk,hk) to the right (to the positive direction) will cause directly the fall of the dominos to its right whose distance from xk is strictly smaller than hk. Similarly, pushing this domino to the left will cause directly the fall of the dominos to its left whose distance from xk is strictly smaller than hk. Clearly, it can cause the fall of other dominos indirectly.

What is the maximal number (M) of dominos that will fall by choosing at most 2 dominos, and pushing them independently to the right or to the left?

Example 1

        x   h
       10  10
       16   5
       18   2
       20   5

By pushing the domino (10,10) to the right, every domino will fall, therefore M=4.

Example 2

         x   h
         0   3
         2   1
        10   3
         8   3
       100   1
     -1000   1

By pushing (0,3) to the right and (10,3) to the left 4 dominos will fall, and no way to get more, therefore M=4.

Example 3

         x     h
        -7     1
        -5     3
        -1     5
         1     5
         5     3
         7     1        

Every domino will fall by pushing (-1,5) to the left and (1,5) to the right.

Input Specification

N
x1 h1
...
xN hN

The first line is the number 1 ≤ N ≤ 105. In the next N lines, the space separated -108 ≤ xk ≤ 108 and 1 ≤ hk ≤ 108 come, k=1...N.

Output Specification

M

A single line with the required M.

Sample Input 1

  1. 4
  2. 16 5
  3. 20 5
  4. 10 10
  5. 18 2
download as text file

Sample Output 1

  1. 4
download as text file

Sample Input 2

  1. 6
  2. 0 3
  3. 2 1
  4. 10 3
  5. 8 3
  6. 100 1
  7. -1000 1
download as text file

Sample Output 2

  1. 4
download as text file

Sample Input 3

  1. 4
  2. 1 1
  3. 2 1
  4. 3 1
  5. 4 1
download as text file

Sample Output 3

  1. 2
download as text file
University of Debrecen; Faculty of Informatics; v. 03/01/2019