Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | strava.in, strava.out | Sursă | ACM ICPC Faza Nationala 2015 |
| Autor | Vlad Duta | Adăugată de |  Duta Vlad •Vman |
| Timp execuţie pe test | 1.9 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
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
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.
Determinati cate suprapuneri de cate doua segmente determina cele N segmente.
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.
Date de ieşire
În fişierul de ieşire strava.out se va afisa pentru fiecare test numarul de suprapuneri determinat.
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
- Se garanteaza ca rezultatul nu depaseste 500 000
Exemplu
| strava.in | strava.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...
