Rays

rays

== include(page="template/taskheader" task_id="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.

Poveste si cerinta...

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

Fisierul de intrare $rays.in$ ...

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

In fisierul de iesire $rays.out$ ...

h2. Restrictii

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

* $... ≤ ... ≤ ...$

h2. Exemplu

table(example). |_. 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
| !problema/rays?poza.bmp! |

table(example). |_. rays.in |_. rays.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|

h3. Explicatie

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

...

== include(page="template/taskfooter" task_id="rays") ==

2491