== 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.
h2. Date de intrare
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.
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
* $T = 5$
* $N = 100 000$
* Toate coordonatele sunt date cu fix 4 zecimale exacte
* Valorile coordonatelor sunt toate in intervalul [$0, 10 000$]
* 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") ==
