Rezolvare PBinfo #950

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.