Se consideră pe axa Ox din plan n puncte distincte reprezentând centrele a n cercuri numerotate cu numerele distincte de la 1 la n. Pentru fiecare cerc k se cunosc abscisa xk a centrului său şi raza sa rk.

Cerința

Să se scrie un program care să determine numărul y maxim de cercuri exterioare două câte două dintre cele n.

Date de intrare

Fișierul de intrare cerc3.in conține pe prima linie pe prima linie, o valoare naturală n, reprezentând numărul de cercuri, iar pe următoarele n linii câte două numere naturale, separate printr-un spaţiu, care reprezintă abscisa x1 a centrului primului cerc şi raza sa r1,…, abscisa xn a centrului celui de-al n-lea cerc şi raza sa rn.

Date de ieșire

Fișierul de ieșire cerc3.out va conține o linie pe care va fi scris numărul natural y reprezentând numărul maxim de cercuri exterioare ale căror centre sunt situate pe axa Ox.

Restricții și precizări

• numerele n, x1,x2,…,xn, r1, r2,…, rn sunt numere naturale
• 1 ≤ n ≤ 300
• 1 ≤ x1,x2,…,xn ≤ 150
• 1 ≤ r1, r2,…, rn ≤ 70
• dacă două cercuri, dintre cele n, au centrele în acelaşi punct de pe axa Ox, atunci razele lor sunt distincte
• două cercuri sunt exterioare dacă nu au niciun punct comun şi nici interioarele lor nu au puncte comune

Exemplu

cerc3.in

8
3 1
1 4
8 1
11 2
15 2
16 6
21 2
21 1

cerc3.out

4

Explicație

Numărul maxim de cercuri exterioare două câte două este y=4. De exemplu, pot fi alese cele 4 cercuri colorate din imaginea de mai jos.

#include <bits/stdc++.h>

using namespace std;

ifstream cin("cerc3.in");
ofstream cout("cerc3.out");

struct elem
{
    int i , j;
}v[501];

int comp(elem a , elem b)
{
    return a.j < b.j || a.j == b.j && a.i < b.i;
}

int main()
{
    int n , cnt = 0 , a , b , inceput = -200;
    cin >> n;
    for(int i = 1 ; i <= n ; i++)
    {
        cin >> a >> b;
        v[i].i = a - b;
        v[i].j = a + b;
    }
    sort(v + 1 , v + n + 1 , comp);

    for(int i = 1 ; i <= n ; i++)
        if(v[i].i > inceput)
        {
            inceput = v[i].j;
            cnt++;
        }
    cout << cnt;
}