Fișierul intrare/ieșire	baloane.in, baloane.out	Sursă	Olimpiada pe Scoala 2012, Clasele 11-12
Autor	Monica Grădinescu	Adăugată de	Victor Manz • vmanz
Timp de execuție pe test	0.5 sec	Limită de memorie	2000 KB
Scorul tău	N/A	Dificultate	1

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Baloane (clasele 11-12)

Notă: această problemă a fost modificată față de original pentru claritate și consistență.

Se dau n baloane sferice, de dimensiuni diferite care coboara vertical. Sa se gaseasca numarul minim de sageti care pleaca de jos in sus, necesar pentru a sparge toate aceste baloane. O sageata sparge toate baloanele aflate pe traiectoria sa. Dacă o săgeată atinge tangențial un balon (doar pe margine) balonul nu se sparge.

Date de intrare

Fișierul de intrare baloane.in contine pe prima linie n, reprezentand numarul de baloane, iar pe urmatoarele n linii, perechi de numere intregi (xi,ri), reprezentand abscisa centrului si respectiv raza fiecarui balon. Fiecare dintre cele n perechi de numere se va afla pe o linie din fisier, elementele perechii fiind separate printr-un spatiu.

Date de ieșire

În fișierul de ieșire baloane.out se va afisa un singur numar, reprezentand numarul minim de sageti necesare.

Restricții

• 1 ≤ n ≤ 100 000
• Pentru 50% din teste 1 ≤ n ≤ 1000
• 0 ≤ xi ≤ 1 000 000
• 1 ≤ ri ≤ 100
• Săgețile pot fi trase din orice punct al abscisei, nu doar din puncte de coordonate întregi.

Exemplu