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