Sa vedem acum o situatie mai concreta. Sa presupunem ca avem $N$ dreptunghiuri in primul cadran al unui plan, cu laturile paralele cu axele de coordonate, iar latura de jos fixata pe axa $OX$. Cum am putea afla aria reuniunii tuturor dreptunghiurilor? De data aceasta, nici macar o solutie naiva nu este multumitoare. Cel mai simplu lucru la care ma gandesc ar fi calcularea ariei folosind principiul includerii si excluderii: se aduna ariile tuturor dreptunghiurilor, se scad ariile comune cator 2 dreptunghiuri, se aduna ariile comune cator 3 dreptunghiuri, etc. Este evident ca aceasta abordare este total nerecomandata din cauza timpului de rulare exponential. Ei bine, solutia la aceasta problema se bazeaza pe o baleiere verticala in care linia de baleiere este plimbata de la stanga la dreapta peste obiecte.

Sa observam mai intai ca laturile verticale ale dreptunghiurilor, precum si latura de jos pot fi ignorate, pastrand doar latura de sus pentru fiecare dreptunghi. Figura initiala este compusa din fasii verticale, fiecare fasie fiind delimitata in partea superioara de un segment (latura de sus a unui dreptunghi initial). Nu ne ramane de facut decat o parcurgere a fiecarei fasii si calcularea ariei acesteia.

Sa observam mai intai ca laturile verticale ale dreptunghiurilor, precum si latura de jos pot fi ignorate, pastrand doar latura de sus pentru fiecare dreptunghi. Figura initiala este compusa din fasii verticale, fiecare fasie fiind delimitata in partea superioara de un segment (latura de sus a unui dreptunghi initial). Nu ne ramane de facut decat o parcurgere a fiecarei fasii si calcularea ariei acesteia, apoi insumarea tuturor.

!algoritmi-de-baleiere?fig2.jpg!