== include(page="template/taskheader" task_id="infasuratoare") ==

*Cosmin, observatii:* merita mentionat ca in puncte distribuite uniform aleator numarul de puncte de pe infasuratoarea convexa este O(log n). Partea cu construirea incrementala a infasuratorii cuonvexe poate merita pusa in un articol nu in problema in care inveti tehnica. Daca vrem sa discutam de probleme inrudite am putea zice de onion peeling (http://www.docstoc.com/docs/2690112/Introduction-to-Convex-Hull-Applications) care s-a dat si la ginfo.

*Cosmin, observatii:* Daca vrem sa discutam de probleme inrudite am putea zice de onion peeling (http://www.docstoc.com/docs/2690112/Introduction-to-Convex-Hull-Applications) care s-a dat si la ginfo.

Dandu-se un set de $N$ puncte in plan, sa se determine poligonul convex de arie minima care are in interiorul lui sau pe margini toate punctele date. Poligonul astfel obtinut se numeste infasuratoarea convexa a celor $N$ puncte.

* $-1.000.000.000 ≤ X{~i~},Y{~i~} ≤ 1.000.000.000$
* $1 ≤ N ≤ 120.000$
* $50%$ din teste sunt generate aleator si astfel au putine puncte pe infasuratoare

* Se recomanda lucrul cu o precizie de {$10^-12^$} pentru

* Se recomanda lucrul cu o precizie de {$10^-12^$} pentru lucrul cu numere reale

h2. Exemplu

*  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 solutie este compusa din 2 pasi unul, sortarea, avand complexitate generala $O(Nlog{~2~}N)$, si dupa 2 stive ambele cu complexitate $O(N)$. O optimizare care se poate aduce deobicei la algoritmul acesta in timp de concurs este ori ca punctele sunt direct sortate, cum este cazul de fata, sau ca punctele au coordonate intregi , moment in care se poate apela la o sortare care se bazeaza pe limitarea capacitatii calculatorului de a tine minte numere intregi foarte mari gen "Radix Sort":http://en.wikipedia.org/wiki/Radix_sort sau cateodata "Counting Sort":http://en.wikipedia.org/wiki/Counting_sort. O astfel de implementare se poate vedea 'aici':job_detail/237258?action=view-source.
 
O alta prezentare a acestei probleme este aceea cand punctele nu sunt toate date deodata, iar fiecare punct este prezentat iterativ. Este destul de clar ca la oricare algoritm dintre cele prezentate pana acum mai apare un $N$ la complexitate, lucru care le face in mare parte ineficiente si inutile pentru problema aceasta.
Un algoritm naiv cu complexitate $O(N*H)$ se poate realiza daca la fiecare aparitie a unui punct se verifica daca acesta este sau nu in poligon. Daca este in poligon nu mai trebuie modificat nimic. Daca nu atunci se cauta primul punct din poligon care unit cu punctul curent nu trece prin interiorul poligonului. Se determina toate aceste puncte si se scot din poligon, dupa care se introduce punctul nou in locul celor scoase.
O observatie matematica care ajuta la optimizarea acestui algoritm este faptul ca in functie de un punct din interiorul poligonului, varfurile par sa fie sortate in functie de unghi si astfel cautarea unui punct care trebuie scos se reduce la o cautare binara de complexitate $O(Nlog{~2~}H)$. Secventa de puncte care trebuie scoase este un interval compact mereu si, astfel, dupa ce se gaseste primul punct se pot determina toate punctele care trebuie scoase printr-o singura parcurgere a lor. Deoarece poligonul poate doar sa se mareasca pe masura ce se introduc puncte, orice punct care se afla in poligon cand este la inceput(la primele 3 puncte) se va afla tot timpul, astfel un punct care se afla mereu in interiorul poligonului este centrul de greutate initial. Dar acum mai trebuie o structura de date care permite stergere, inserare si cautare in $O(log{~2~}N)$. O astfel de structura de date este "Arborele Echilibrati de cautare":http://en.wikipedia.org/wiki/Self-balancing_binary_search_tree, care este implementata deja in stl sub forma de "set-uri":http://www.sgi.com/tech/stl/set.html. O astfel de solutie are complexitate $O(Nlog{~2~}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