p<>. Se considera $N&le;50 000$ dreptunghiuri in plan, fiecare avand laturile paralele cu axele $OX, OY$. Lungimea marginilor (contururilor) reuniunii tuturor dreptunghiurilor se va numi "perimetru". Sa se calculeze perimetrul celor $N$ dreptunghiuri.

p<>. In fisierul $drept.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 fiÅŸierul $drept.out$.

p<>. In fisierul $drept.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 $drept.out$.

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

p<>. In fisierul $puncte.in$ se vor gasi pe prima linie numerele $N$ si $M$. Pe urmatoarele $N$ linii se vor gasi coordonatele punctelor. Pe urmatoarele $M$ linii se vor gasi cate patru numere naturale reprezentand coordonatele colturilor dreptunghiurilor.

p<>. In fisierul $puncte.out$ se vor gasi $M$ numere naturale reprezentand raspunsurile la întrebari.

p<>. In fisierul $puncte.out$ se vor gasi $M$ numere naturale reprezentand raspunsurile la întrebari.

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

p<>. Pentru fiecare dreptunghi, se executa cautarea in arborele de intervale pentru segmentul $[x1, x2]$ (deoarece se folosesc doar cele $N$ coordonate $x$ ale punctelor, se vor potrivi capetele acestui interval folosind cautarea binara la cea mai apropiata coordonata $x$ de fiecare capat). Pentru fiecare interval din arbore atins, se executa doua cautari binare printre coordonatele y corespunzatoare coordonatelor x din acel interval, pentru a determina cate puncte din intervalul respectiv se afla in intervalul $[y1, y2]$ (adica in interiorul dreptunghiului).

p<>. Complexitatea $O(log{~2~}^2^ N)$ poate fi redusa, folosind o metoda descoperita independent de Willard si Lueker in anul $1978$. Se observa ca pentru fiecare coordonata $y$ dintr-un nod, daca presupunem ca se efectueaza o cautare binara, atunci putem determina in timpul interclasarii pozitia din fiecare fiu pe care o va returna cautarea binara pentru aceeasi valoare. Este evident ca pentru o valoare $y$ dintr-un nod care a provenit dintr-un fiu in timpul interclasarii, exista o unica valoare maxima $y'$ din celalalt fiu astfel incat $y'&le;y$. Asadar, tinem pentru fiecare valoare $y$ dintr-un nod doi indici care identifica pozitiile corespunzatoare efectuarii unei cautari binare in fii pentru valoarea $y$. Astfel, in timpul cautarii, in loc sa se efectueze cautari binare, se pot parcurge acesti indici, care oferă in $O(1)$ pozitia in lista cautata, reducand complexitatea totala la $O(log{~2~} N)$.

p<>. Complexitatea $O(log{~2~}^2^ N)$ poate fi redusa, folosind o metoda descoperita independent de Willard si Lueker in anul $1978$. Se observa ca pentru fiecare coordonata $y$ dintr-un nod, daca presupunem ca se efectueaza o cautare binara, atunci putem determina in timpul interclasarii pozitia din fiecare fiu pe care o va returna cautarea binara pentru aceeasi valoare. Este evident ca pentru o valoare $y$ dintr-un nod care a provenit dintr-un fiu in timpul interclasarii, exista o unica valoare maxima $y'$ din celalalt fiu astfel incat $y'&le;y$. Asadar, tinem pentru fiecare valoare $y$ dintr-un nod doi indici care identifica pozitiile corespunzatoare efectuarii unei cautari binare in fii pentru valoarea $y$. Astfel, in timpul cautarii, in loc sa se efectueze cautari binare, se pot parcurge acesti indici, care ofera in $O(1)$ pozitia in lista cautata, reducand complexitatea totala la $O(log{~2~} N)$.