Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | rays.in, rays.out | Sursă | preONI 2008 Runda 2 |
| Autor | Filip Cristian Buruiana | Adăugată de |  Airinei Adrian •astronomy |
| Timp execuţie pe test | 0.2 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/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.in | rays.out | Figura |
|---|---|---|
| 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.
