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

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. Acest poligon se mai numeste si infasuratoarea convexa a punctelor.

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.

h2. Date de intrare

În fişierul de intrare $infasuratoare.in$ se va gasi pe prima linie un numar natural $N$, care reprezinta numarul de puncte. Pe urmatoarele $N$ linii se vor gasi cate doua numere rationale $X{~i~}, Y{~i~}$ care reprezinta coordonatele punctului $i$.

În fişierul de intrare $infasuratoare.in$ se va gasi pe prima linie un numar natural $N$, care reprezinta numarul de puncte din set. Pe fiecare din urmatoarele $N$ linii se va gasi o pereche de numere rationale $X{~i~}, Y{~i~}$ care reprezinta coordonatele punctului $i$.

h2. Date de ieşire

Pe prima linie a fişierul de ieşire $infasuratoare.out$ se va afla $P$, numarul de puncte de pe infasuratoarea convexa. Pe urmatoarele $P$ linii se vor gasi cele $P$ puncte ce alcatuiesc poligonul in ordine invers trigonometrica, incepand cu cel mai de jos, iar in caz de egalitate cel mai din stanga.

Pe prima linie a fişierului de ieşire $infasuratoare.out$ se va afla $H$, numarul de puncte de pe infasuratoarea convexa. Pe urmatoarele $H$ linii se vor gasi cele $H$ puncte ce alcatuiesc poligonul, in ordine invers trigonometrica, incepand cu cel mai de jos (punctul cu ordonata minima), iar in caz de egalitate cu cel mai din stanga (punctul cu abscisa minima).

h2. Restricţii
* $-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.

* $1 ≤ N ≤ 120.000$
* $50%$ din teste sunt generate aleator si astfel au putine puncte pe infasuratoare

h2. Exemplu

h2. Indicatii de rezolvare

Pentru usurinta intelegerii rezolvarii se face urmatoarea notatie: notam $H$ ca fiind numarul de varfuri ale infasuratorii convexe.
O prima observatie esentiala este ca varfurile acestui poligon sunt puncte din acele $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 cel mai din stang. Dupa ce s-a ales acest punct se incearca toate punctele si se alege punctul care face o intoarcere cat mai puternica spre stanga cu punctul curent, aceasta se face in {$O(N)$}. Acest punct la randul lui se afla pe infasuratoare deoarece nu exista nici un alt punct care unit cu primul sa il acopere. Se continua algoritmul cu punctul tocmai ales. Aceasta solutie face $O(N)$ pasi pentru fiecare punct de pe infasuratoare convexa, deci complexitatea finala ar fi $O(N*H)$. In caz general, pentru teste generate random aceasta solutie face un numar mic de pasi, dar pentru teste generate inteligent poate face aproximativ $O(N^2^)$ pasi. Aceast algoritm se numeste "Jarvis March":http://www.cs.princeton.edu/~ah/alg_anim/version1/JarvisMarch.html. O sursa se poate vedea 'aici':job_detail/236569?action=view-source. Aceasta solutie 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 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.

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.