Fişierul intrare/ieşire:rays.in, rays.outSursăpreONI 2008 Runda 2
AutorFilip Cristian BuruianaAdăugată deastronomyAirinei Adrian astronomy
Timp execuţie pe test0.4 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Rays

Cezara se afla in centrul sistemului de coordonate cartezian (in punctul 0, 0) si are un pistol cu gloante speciale. Folosind acest pistol isi propune sa distruga toate cele N segmente paralele cu axa Oy situate in stanga si in dreapta ei. Ea poate orienta pistolul la orice unghi intre 0 si 360 si poate trage un glont in acea directie. Glontul va trece prin toate segmentele ce le poate atinge si le va distruge instantaneu. Deoarece gloantele sunt costisitoare, ea isi propune sa foloseasca cat mai putine gloante.

Date de intrare

Fisierul de intrare rays.in contine pe prima linie numarul N avand semnificatia din enunt. Pe urmatoarele N linii urmeaza cate trei numere x y1 y2, (x y1) si (x y2) reprezentand capetele segmentului paralel cu axa Oy.

Date de iesire

Pe prima linie a fisierului de iesire rays.out se afla un singur numar MIN reprezentand numarul minim de trageri ce este necesar pentru a distruge toate segmentele.

Restrictii

  • 1 ≤ N ≤ 200 000
  • Toate coordonatele sunt numere intregi, iar valoarea lor in modul este mai mica sau egala decat 109
  • Nu va exista niciun segment situat pe axa Oy

Exemplu

rays.inrays.outFigura
6
-3 0 2
-4 2 4
3 1 -2
3 2 6
4 -1 -5
5 -8 3
3

Explicatie

In figura, segmentele sunt reprezentate de culoarea albastra iar sagetile rosii reprezinta directia in care au fost trase gloantele.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content