== include(page="template/taskheader" task_id="nn") ==
Poveste şi cerinţă...
Marele inginer NN, expert în construirea de baraje, a primit de data aceasta o sarcină mai îmbârligată. Acesta are de construit $M$ baraje peste mai multe râuri dintr-o deltă şi îşi planifică pe hârtie milimetrică construcţia fiecărui baraj în parte.
Toate râurile peste care are de construit baraje sunt braţe ale aceluiaşi fluviu şi toate pornesc din exact acelaşi punct pe lungimea fluviului. Pentru a-şi explica schiţa, $NN$ marchează locul de despărţire a tuturor braţelor fluviului printr-un punct $O$, numit origine. Apoi, din origine pornesc $N$ semidrepte, fiecare reprezentând o porţiune de uscat, astfel încât spaţiul gol dintre $2$ semidrepte consecutive va fi considerat un braţ al fluviului.
După ce a desenat schiţa proiectului, NN se întreabă care e numărul de râuri pe care le acoperă complet fiecare baraj. Un baraj acoperă complet un râu dacă intersectează fiecare dintre malurile acestuia. Sarcina voastră este să îl ajutaţi oferindu-i informaţii precise pentru a-şi putea realiza planul cât mai eficient, păstrându-şi renumele.
h2. Date de intrare
Fişierul de intrare $nn.in$ ...
Pe prima linie a fişierului $nn.in$ se află $N$ şi $M$, reprezentând numărul de semidrepte, respectiv numărul de baraje. Pe fiecare dintre următoarele $N$ linii se vor afla informaţii despre cele $N$ semidrepte, astfel: pe linia $i$ ([$1 ≤ i ≤ N$]) se află o pereche de numere naturale $x$ şi $y$, reprezentând coordonatele unui punct aflat pe semidreapta $i$ (ştim deja că toate semidreptele pornesc din $O(0, 0)$). Pe fiecare dintre următoarele M linii se vor afla câte 4 numere $x[~1~]$, $y[~1~]$, $x[~2~]$, $y[~2~]$ reprezentând faptul că există un baraj care are extremităţile în punctele de coordonate $(x[~1~], y[~1~])$ şi $(x[~2~], y[~2~])$.
h2. Date de ieşire
În fişierul de ieşire $nn.out$ ...
În fişierul de ieşire $nn.out$ se vor afişa $M$ numere, fiecare pe o linie separată, reprezentând numărul de râuri blocate de fiecare dintre cele $M$ baraje. În rezolvarea problemei nu se va ţine cont de grosimea barajului, aceasta fiind neglijabilă.
h2. Restricţii
* $... ≤ ... ≤ ...$
* Toate numerele din fişierul de intrare sunt naturale ≤ 10^5^
* Nici un punct din fişier nu coincide cu originea
* Pentru $10%$ din teste $N = 2, M = 1$
* Pentru următoarele $20%$ din teste, capetele segmentelor (barajelor) se vor afla pe semidreptele din datele de intrare
* Pentru primele $50%$ din teste $N, M ≤ 1000$
* *Se recomanda folosirea tipului long double pentru lucrul cu numere rationale.*
h2. Exemplu
table(example). |_. nn.in |_. nn.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 5 3
5 1
2 1
2 5
5 5
0 4
3 0 4 2
1 4 3 1
5 3 7 6
| 1
2
0
|
h3. Explicaţie
...
!problema/nn?exemplu.png!
== include(page="template/taskfooter" task_id="nn") ==
== include(page="template/taskfooter" task_id="nn") ==
