h1. Arbori de intervale si aplicatii in geometria computationala
(Categoria _Structuri de date_, autor _Dana Lica_)

Exemplu:
|_. segment.in |_. segment.out |_. Figura |

|^. $5$
$2 9 13  9$
$4 6 12  6$
$1 2  6  2$
$5 0  5  8$
$7 5  7 11$  |^. $4$ |=. !arbori-de-intervale?figure-1.jpg! |

|^. 5
2 9 13  9
4 6 12  6
1 2  6  2
5 0  5  8
7 5  7 11  |^. 4 |=. !arbori-de-intervale?figure-1.jpg! |

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.

!arbori-de-intervale?figure7.jpg!

h2. Probleme propuse
 
1) (preluata de la Olimpiada Baltica de Informatica, Polonia  2001)
 
p<>. Se considera $N&le;50 000$ dreptunghiuri in plan, fiecare avand laturile paralele cu axele $OX, OY$. Sa se calculeze aria ocupata de reuniunea celor $N$ dreptunghiuri.
 
p<>. In fisierul $drept2.in$ se gaseste pe prima linie numarul $N$ de dreptunghiuri, iar pe fiecare din urmatoarele $N$ linii cate patru numere naturale mai mici ca $50 000$, reprezentand coordonatele carteziene ale coltului stanga sus, respectiv dreapta jos ale fiecarui dreptunghi. Rezultatul se va scrie in fisierul $drept2.out$.
 
p<>. Timp maxim de executie: $1 secunda / test$
 
2) (preluata de la Olimpiada Nationala de Informatica, Polonia 2001)
 
p<>. Se considera $N&le;50 000$ puncte in plan de coordonate numere naturale mai mici ca $50 000$. Sa se determine unde se poate aseza un dreptunghi de lungime $DX$ si latime $DY$ astfel incat numarul de puncte incluse in dreptunghi sa fie maxim.
 
p<>. In fisierul $puncte.in$ se gasesc pe prima linie numerele $N$, $DX$ si $DY$. Pe urmatoarele $N$ linii se gasesc coordonatele punctelor.
 
p<>. In fisierul $puncte.out$ se vor gasi cinci numere naturale reprezentand coordonatele colturilor stanga sus si dreapta jos ale asezarii dreptunghiului si numarul maxim de puncte din dreptunghi.
 
p<>. Timp maxim de executie: $1 secunda / test$
 
3) (preluata de la Barajul pentru Lotul National, Romania 2003)
 
p<>. Se considera $N&le;100 000$ puncte in plan de coordonate numere naturale mai mici ca $100 000$. Sa se determine unde se pot aseza doua dreptunghiuri de lungime $DX$ si latime $DY$, fara sa se intersecteze, astfel incat numarul de puncte incluse in cele doua dreptunghiuri sa fie maxim.
 
p<>. In fisierul $puncte2.in$ se gasesc pe prima linie numerele $N$, $DX$ si $DY$. Pe urmatoarele $N$ linii se gasesc coordonatele punctelor.
 
p<>. In fişierul $puncte2.out$ se vor gasi $9$ numere naturale reprezentand coordonatele colturilor stanga sus si dreapta jos ale asezarii primului dreptunghi, respectiv a celui de-al doilea, cat si numărul maxim de puncte incluse in ambele dreptunghiuri.
 
p<>. Timp maxim de executie: $1 secunda / test$
 
4) (preluata de la concursul international USACO January Open, 2004)
 
p<>. Se considera $N&le;250 000$ dreptunghiuri in plan, fiecare avand laturile paralele cu axele $OX/OY$, care nu se intersecteaza si nu se ating, dar pot fi incluse unul in altul. Se numeste "inchisoare" un dreptunghi inconjurat de alte dreptunghiuri. Sa se determine numarul maxim de dreptunghiuri de care poate fi înconjurata o "inchisoare" si cate astfel de "inchisori" maxime exista.
 
p<>. In fisierul $inchis.in$ se gaseste pe prima linie numarul $N$ de dreptunghiuri, iar pe fiecare din urmatoarele $N$ linii cate patru numere naturale mai mici ca $1 000 000 000$, reprezentand coordonatele carteziene ale coltului stanga sus, respectiv dreapta jos ale fiecarui dreptunghi.
 
p<>. In fisierul $inchis.out$ se gasesc doua numere naturale: numarul maxim de dreptunghiuri de care poate fi inconjurata o "inchisoare" si cate astfel de "inchisori" maxime exista.

p<>. Timp maxim de execuyie: $1 secunda / test$