h2. Indicatii de rezolvare

Fie $H$ numarul de varfuri al infasuratorii convexe. O prima observatie esentiala este ca varfurile poligonului solutie sunt puncte din setul celor $N$ puncte date initial.
Cu aceasta observatie se poate implementa urmatorul algoritm naiv si usor de implementat. Se incepe cu un punct care se afla sigur pe infasuratoare. Sa presupun ca il alegem pe cel mai de jos si in caz de egalitate pe cel mai din stanga. Dupa ce s-a ales acest punct se incearca toate punctele si se alege punctul care face o intoarcere de unghi maxim spre stanga cu punctul curent. Acest pas se poate face in {$O(N)$}. Punctul nou determinat se afla la randul lui pe infasuratoare deoarece nu exista niciun alt punct care unit cu primul sa il acopere. Se repeta pasul anterior, de fiecare data cu ultimul punct ales, pana cand ajungem din nou la punctul de pornire. Aceasta solutie face $O(N)$ pasi pentru fiecare punct de pe infasuratoare convexa, deci complexitatea finala este $O(N*H)$. Pe teste generate aleator aceasta solutie face un numar mic de operatii deoarece $H$ este mic in comparatie cu $N$, dar pentru teste generate inteligent, cand $H$ este de ordinul {$O(N)$}, algoritmul executa $O(N^2^)$ pasi. Aceast algoritm este cunoscut ca "potrivirea lui Jarvis":http://www.cs.princeton.edu/~ah/alg_anim/version1/JarvisMarch.html, sau {_impachetarea pachetului_}. O sursa folosind acest algoritm se poate vedea 'aici':job_detail/236569?action=view-source, si obtine $50$ de puncte.

Fie $H$ numarul de varfuri al infasuratorii convexe. O prima observatie esentiala este ca varfurile poligonului solutie sunt puncte din setul celor $N$ puncte date initial.
Cu aceasta observatie se poate implementa urmatorul algoritm naiv si usor de implementat. Se incepe cu un punct care se afla sigur pe infasuratoare. Sa presupunem ca il alegem pe cel mai de jos si in caz de egalitate pe cel mai din stanga. Dupa ce s-a ales acest punct se incearca toate punctele si se alege punctul care face o intoarcere de unghi maxim spre stanga cu punctul curent. Acest pas se poate face in {$O(N)$}. Punctul nou determinat se afla la randul lui pe infasuratoare deoarece nu exista niciun alt punct care unit cu primul sa il acopere. Se repeta pasul anterior, de fiecare data cu ultimul punct ales, pana cand ajungem din nou la punctul de pornire. Aceasta solutie face $O(N)$ pasi pentru fiecare punct de pe infasuratoare convexa, deci complexitatea finala este $O(N*H)$. Pe teste generate aleator aceasta solutie face un numar mic de operatii deoarece $H$ este mic in comparatie cu $N$, dar pentru teste generate inteligent, cand $H$ este de ordinul {$O(N)$}, algoritmul executa $O(N^2^)$ pasi. Aceast algoritm este cunoscut ca "potrivirea lui Jarvis":http://www.cs.princeton.edu/~ah/alg_anim/version1/JarvisMarch.html, sau {_impachetarea pachetului_}. O sursa folosind acest algoritm se poate vedea 'aici':job_detail/236569?action=view-source, si obtine $50$ de puncte.
 
O alta solutie se bazeaza pe sortarea dupa unghi. Se alege un punct care sa fie sigur pe infasuratoare: cel mai de jos punct, iar in caz de egalitate cel mai din stanga. Se sorteaza toate punctele in functie de panta dreptei care uneste punctul ales de restul punctelor (unghiul polar), dupa care se construieste o stiva care retine in fiecare moment infasuratoare convexa curenta. Atunci cand un punct este introdus in stiva va scoate puncte pana cand acesta formeaza cu dreapta definita de ultimele $2$ puncte din stiva un unghi mai mic de $180$ de grade. Repetand procedeul pentru fiecare punct se va inchide poligonul. Acest algoritm se numeste "scanarea Graham":http://www.cs.princeton.edu/~ah/alg_anim/version1/GrahamScan.html. Complexitatea sortarii punctelor va fi {$O(Nlog{~2~}N)$}, iar complexitatea construirii propriu-zise a poligonului va fi liniara, deoarece fiecare pas are complexitatea {$O(1)$} amortizat. Complexitatea finala va fi deci $O(Nlog{~2~}N)$. O astfel de implementare se poate vedea 'aici':job_detail/236216?action=view-source.

O alta solutie se bazeaza pe sortarea dupa unghi. Se alege un punct care sa fie sigur pe infasuratoare, sa presupunem ca e cel mai de jos punct. Se sorteaza toate punctele in functie de panta dreptei care uneste punctul ales de restul punctelor. Dupa care se construieste o stiva care tine in fiecare moment infasuratoare convexa curenta. Un punct cand este introdus in stiva va scoate puncte pana cand acesta formeaza cu dreapta definita de ultimele $2$ puncte din stiva un unghi mai mic de $180$ grade, si astfel se tot inchide poligonul. Acest algoritm se numeste "Graham Scan":http://www.cs.princeton.edu/~ah/alg_anim/version1/GrahamScan.html. Complexitatea sortarii este $O(Nlog{~2~}N)$ iar complexitatea stivei este de $O(N)$, complexitatea totala fiind de $O(NlogN + N)$.
O astfel de implementare se poate vedea 'aici':job_detail/236216?action=view-source.

O alta solutie care are complexitate tot $O(Nlog{~2~}N)$, dar care se poate imbunatati, este compusa din urmatorii pasi:
*  Se sorteaza punctele dupa x iar in caz de egalitate dupa y