h2. Problema 1

p<>. Se considera $N&le;50 000$ segmente in plan dispuse paralel cu axele OX si OY. Sa se determine care este numarul total de intersectii dintre segmente.

p<>. Se considera $N (N&le;50 000)$ segmente in plan dispuse paralel cu axele OX si OY. Sa se determine care este numarul total de intersectii dintre segmente.

p<>. 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_$.

      returneaza structura auxiliara din fiul stang combinata cu cea din fiul drept
==

p<>. Vom demonstra in continuare ca operatiile prezentate mai sus au complexitatea $O(log{~2~} N)$ pentru un arbore de $N$ intervale. Este posibil ca intr-un nod sa aiba loc apel atat in fiul stang cat si in cel drept. Acest lucru produce un cost aditional doar prima data cand are loc. Dupa prima "rupere in doua", oricare astfel de "rupere" nu va aduce cost aditional, deoarece unul din fii va fi mereu inclus complet in intervalul $[a,b]$. Cum inaltimea arborelui, pentru $N$ intervale, este $[log{~2~}N]+1$, complexitatea operatiilor va fi tot $O(log{~2~} N)$.

p<>. Vom demonstra in continuare ca operatiile prezentate mai sus au complexitatea $O(log{~2~} N)$ pentru un arbore de $N$ intervale. Este posibil ca intr-un nod sa aiba loc apel atat in fiul stang cat si in cel drept. Acest lucru produce un cost aditional doar prima data cand are loc. Dupa prima "rupere in doua", oricare astfel de "rupere" nu va aduce cost aditional, deoarece unul din fii va fi mereu inclus complet in intervalul $[a,b]$. Cum inaltimea arborelui, pentru $N$ intervale, este $[log{~2~}N]+1$, complexitatea operatiilor va fi tot $O(log{~2~} N)$.
 
p<>. Pentru a retine in memorie un arbore de intervale pentru $N$ valori, vom aveam de nevoie de $N+N/2+N/4+N/8...=2*N-1$ locatii de memorie (sunt $2*N-1$ noduri). Deoarece arborele nu este complet, trebuie verificat de fiecare data daca fii unui nod exista in arbore (aceasta verificare a fost omisa in pseudocodul de mai sus), altfel s-ar incerca accesarea de valori din vector care nu exista. Daca memorie disponibila in timpul concursului este suficienta, se poate declara vectorul care retine arborele de intervale de lungime $2^K^$ astfel incat $2^K^&ge;2*N-1$, simuland astfel un arbore complet si nefiind necesare verificarile mentionate mai sus.