Diferențe pentru problema/baloane între reviziile #2 si #6

== include(page="template/taskheader" task_id="baloane") ==

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.)

_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.

h2. 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 reale, reprezentand abscisa centrului si raza fiecarui balon.

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.

h2. Date de ieșire

* $1 ≤ n ≤ 100 000$
* Pentru 50% din teste $1 ≤ n ≤ 1000$

* $0 ≤ xi ≤ 1 000 000 000$
 
 

* $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.

h2. Exemplu
table(example).
|_. baloane.in |_. baloane.out |
| 3

3.5   2
3      1.5
7.3   2

3 2
3 1
7 2

| 2
|