== include(page="template/taskheader" task_id="strava") ==
Se dau N segmente in plan. Atribuim fiecarui segment determinat de punctele (X1, Y1) respectiv (X2, Y2) un sens de la (X1, Y1) catre (X2, Y2). Spunem ca doua segmente determinate de punctele (S1X1, S1Y1, S1X2, S1Y2), respectiv (S2X1, S2Y1, S2X2, S2Y2) se suprapun daca si numai daca
Se dau $N$ segmente in plan. Atribuim fiecarui segment determinat de punctele $(X1, Y1)$ respectiv $(X2, Y2)$ un sens de la $(X1, Y1)$ catre $(X2, Y2)$. Spunem ca doua segmente determinate de punctele $(S1X1, S1Y1, S1X2, S1Y2)$, respectiv $(S2X1, S2Y1, S2X2, S2Y2)$ se suprapun daca si numai daca sunt satisfacute simultan urmatoarele doua conditii:
D(S1X1, S1Y1)(S2X1, S2Y1) <= 1
D(S1X2, S1Y2)(S2X2, S2Y2) <= 1
$D(S1X1, S1Y1)(S2X1, S2Y1)$ <= $1$
$D(S1X2, S1Y2)(S2X2, S2Y2)$ <= $1$
unde prin D(P1)(P2) am notat distanta euclidiana intre punctele P1, respectiv P2.
unde prin $D(P1)(P2)$ am notat distanta euclidiana intre punctele $P1$, respectiv $P2$.
Determinati cate suprapuneri de cate doua segmente determina cele N segmente.
Determinati cate suprapuneri de cate doua segmente determina cele $N$ segmente.
h2. Date de intrare
Fişierul de intrare $strava.in$ ...
Fişierul de intrare $strava.in$ contine pe prima linie un numar natural $T$ reprezentand numarul de teste. Pentru fiecare test urmeaza pe o linie noua valoarea lui $N$ reprezentand numarul de segmente urmata de $N$ linii a cate 4 numere $(X1, Y1, X2, Y2)$ reprezentand coordonatele capetelor segmentelor.
h2. Date de ieşire
În fişierul de ieşire $strava.out$ ...
În fişierul de ieşire $strava.out$ se va afisa pentru fiecare test numarul de suprapuneri determinat.
h2. Restricţii
* $N = 33 554 432$
* $T = 5$
* $N = 100 000$
* Toate coordonatele sunt date cu fix 4 zecimale exacte
* Valorile coordonatelor sunt toate in intervalul $[0, 10 000]$
* Se garanteaza ca rezultatul nu depaseste $500 000$
h2. Exemplu
table(example). |_. strava.in |_. strava.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 1
3
1.0000 1.0000 5.0000 5.0000
1.1000 0.9000 4.9000 5.1000
5.0000 5.0000 1.0000 1.0000
| 1
|
h3. Explicaţie
...
== include(page="template/taskfooter" task_id="strava") ==
