Fişierul intrare/ieşire:baloane.in, baloane.outSursăOlimpiada pe Scoala 2012, Clasele 11-12
AutorMonica GradinescuAdăugată devmanzVictor Manz vmanz
Timp execuţie pe test0.5 secLimită de memorie2000 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

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

baloane.inbaloane.out
3
3 2
3 1
7 2
2
Trebuie sa te autentifici pentru a trimite solutii. Click aici