Fişierul intrare/ieşire:strava.in, strava.outSursăACM ICPC Faza Nationala 2015
AutorVlad DutaAdăugată deVmanDuta Vlad Vman
Timp execuţie pe test3.8 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/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 sunt satisfacute simultan urmatoarele doua conditii:

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.instrava.out
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
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?