Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2007-04-17 21:24:28.
Revizia anterioară Revizia următoare
Revizia anterioară Revizia următoare
Arbori de intervale si aplicatii in geometria computationala
(Categoria Structuri de date, autor Dana Lica)
Problema 1
Se considera N<=50 000 segmente in plan dispuse paralel cu axele OX si OY. Sa se determine care este numarul total de intersectii dintre segmente.
In fisierul segment.in se gaseste pe prima linie numarul N de segmente, iar pe fiecare dintre urmatoarele N linii cate patru numere naturale mai mici decat 50 000, reprezentand coordonatele carteziene ale extremitatilor fiecarui segment.
Rezultatul se va scrie in segment.out.
Timp de executie: 1 secunda/test
Exemplu:
| segment.in | segment.out |
|---|---|
| 5 2 9 13 9 4 6 12 6 1 2 6 2 5 0 5 8 7 5 7 11 | 4 |
