h2. 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.
p<>. 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.
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_$.
Timp de executie: $1 secunda/test$
Exemplu:
$5 0 5 8$
$7 5 7 11$ |^. $4$ |=. !arbori-de-intervale?figure1.jpg! |
Folosind cunostinte generale de geometrie analitica se poate obtine un algoritm $O(N^2^)$ dar acesta nu se va incadra in limita de timp.
p<>. Folosind cunostinte generale de geometrie analitica se poate obtine un algoritm $O(N^2^)$ dar acesta nu se va incadra in limita de timp.
h2. Algoritmi de "baleiere" _(line sweeping)_
Pentru rezolvarea acestei probleme vom folosi o tehnica cunoscuta sub numele de "baleiere" _(sweeping)_ care este comuna multor algoritmi de geometrie computationala. In baleiere, o dreapta de baleiere verticala, imaginara, traverseaza multimea obiectelor geometrice, de obicei de la stanga la dreapta. Baleierea ofera o metoda pentru ordonarea obiectelor geometrice, plasandu-le intr-o structura de date, pentru obtinerea relatiilor dintre ele.
p<>. Pentru rezolvarea acestei probleme vom folosi o tehnica cunoscuta sub numele de "baleiere" _(sweeping)_ care este comuna multor algoritmi de geometrie computationala. In baleiere, o dreapta de baleiere verticala, imaginara, traverseaza multimea obiectelor geometrice, de obicei de la stanga la dreapta. Baleierea ofera o metoda pentru ordonarea obiectelor geometrice, plasandu-le intr-o structura de date, pentru obtinerea relatiilor dintre ele.
Algoritmii de baleiere gestioneaza doua multimi de date:
# +Starea liniei+ de baleiere da relatia dintre obiectele intersectate de linia de baleiere
# +Lista punct-eveniment+ este o secventa de coordonate $x$, ordonate de la stanga la dreapta de obicei, care definesc pozitiile de oprire ale dreptei de baleiere; fiecare astfel de pozitie de oprire se numeste _punct eveniment_; numai in punctele eveniment se intalnesc modificari ale starii liniei de baleiere; pentru unii algoritmi, lista punct-eveniment este determinata dinamic in timpul executiei algoritmului.
Pentru a rezolva problema, vom deplasa o dreapta de baleiere verticala, imaginara de la stanga la dreapta. Lista punct-eveniment va contine capetele segmentelor orizontale, ce fel de tip sunt (cap stanga sau cap dreapta) si segmentele verticale. Pe masura ce ne deplasam de la stanga la dreapta vom efectua urmatoarele operatii:
p<>. Pentru a rezolva problema, vom deplasa o dreapta de baleiere verticala, imaginara de la stanga la dreapta. Lista punct-eveniment va contine capetele segmentelor orizontale, ce fel de tip sunt (cap stanga sau cap dreapta) si segmentele verticale. Pe masura ce ne deplasam de la stanga la dreapta vom efectua urmatoarele operatii:
* cand intalnim un capat stang, inseram capatul in starile dreptei de baleiere;
* cand intalnim un capat drept, stergem capatul din starile dreptei de baleiere;
* cand intalnim un segment vertical, numarul de intersectii ale acestui segment cu alte segmente orizontale va fi dat de numarul capetelor de intervale care se afla in starile dreptei de baleiere cuprinse intre coordonatele $y$ ale segmentului vertical.
p<>. Astfel, starile dreptei de baleiere sunt o structura de date pentru care avem nevoie de urmatoarele operatii:
* **INSEREAZA(y)** : insereaza capatul $y$
* **STERGE(y)** : sterge capatul $y$
* **INTEROGARE(y1,y2)** : intoarce numarul de capete cuprinse in intervalul $[y1, y2]$
p<>. Fie $MAXC$ valoarea maxima a coordonatelor capetelor de segmente. Folosind un vector pentru a implementa aceste operatiile descrise mai sus vom obtine o complexitate $O(1)$ pentru primele doua operatii si $O(MAXC)$ pentru cea de-a treia. Astfel, complexitatea va fi $O(N*MAXC)$ in cazul cel mai defavorabil. Putem comprima spatiul $[0...MAXC]$ observand ca doar maxim N din valori din acest interval conteaza, si anume capetele segmentelor orizontale, astfel reducand a treia operatie la $O(N)$, dar algoritmul va avea complexitatea $O(N^2^)$, ceea ce nu aduce nici o imbunatatire fata de algoritmul trivial.
p<>. Aceasta situatie ne indeamna sa cautam o structura de date mai eficienta. O prima varianta ar fi impartirea vectorului in bucati de sqrt(N) reducand complexitatea totala la $O(N*sqrt(N))$. In continuare vom prezenta o structura de date care ofera o complexitate logaritmica pentru operatiile descrise mai sus.
h2. Arbori de intervale
Un arbore de intervale este un arbore binar in care fiecare nod poate avea asociata o structura auxiliara(anumite informatii). Dandu-se doua numere intregi $st$ si $dr$, cu $st<dr$, atunci arborele de intervale T(st,dr) se construieste recursiv astfel:
