!> problema/infasuratoare/?pic1.bmp!
*  Se sorteaza punctele dupa {$x$}, iar in caz de egalitate dupa $y$

*  Se aleg cel mai din stanga si cel mai din dreapta punct si se desparte problema in $2$ subprobleme similare. Pe fiecare parte a dreptei determinata de cele doua puncte trebuie sa fie gasita infasuratoarea. Aceasta se realizeaza cu o stiva foarte asemanatoare cu cea prezentata anterior. Cat timp de ambele parti ale dreptei este respectata convexitatea si ambele parti incep si se termina cu punctele alese (cel mai din stanga si cel mai din dreapta), reuninuea lor va reprezenta infasuratoarea convexa a tuturor punctelor. O astfel de implementare se poate vedea 'aici':job_detail/237301?action=view-source.

*  Se aleg cel mai din stanga si cel mai din dreapta punct si se desparte problema in $2$ subprobleme similare. Pe fiecare parte a dreptei determinata de cele doua puncte trebuie sa fie gasita infasuratoarea. Aceasta se realizeaza cu o stiva foarte asemanatoare cu cea prezentata anterior. Cat timp de ambele parti ale dreptei este respectata convexitatea si ambele parti incep si se termina cu punctele alese (cel mai din stanga si cel mai din dreapta), reuninuea lor va reprezenta infasuratoarea convexa a tuturor punctelor.

O optimizare care se poate aduce este atunci cand punctele au coordonate intregi, cand putem folosi in pasul de sortare algoritmi precum "Radix Sort":http://en.wikipedia.org/wiki/Radix_sort sau, uneori, "Counting Sort":http://en.wikipedia.org/wiki/Counting_sort. In plus, daca punctele sunt direct sortate, complexitatea devine {$O(N)$}.

O optimizare care se poate aduce este atunci cand punctele au coordonate intregi, cand putem folosi in pasul de sortare algoritmi precum "Radix Sort":http://en.wikipedia.org/wiki/Radix_sort sau, uneori, "Counting Sort":http://en.wikipedia.org/wiki/Counting_sort. In plus, daca punctele sunt direct sortate, complexitatea devine {$O(N)$}. O astfel de implementare se poate vedea 'aici':job_detail/237258?action=view-source.

h2. Aplicaţii