h2. Date de ieşire

În fişierul de ieşire $infasuratoare.out$ va fi o singura linie cu aria poligonului cerut cu 4 zecimale si se va accepta o eroare de precizie de 10^-4^.

În fişierul de ieşire $infasuratoare.out$ va fi o singura linie cu aria poligonului cerut

h2. Restricţii

* Pentru inca $60%$ din teste $N ≤ 110.000$.
* Pentru ultimele $20%$ din teste $N ≤ 1.000.000$ si punctele vor fi sortate dupa $X$ si in caz de egalitate dupa $Y$.
* De asemenea pentru primele $50%$ din teste punctele sunt generate random, astfel incat numarul de puncte de pe infasuratoarea convexa va fi mic.

* Oricare $3$ puncte nu vor fi coliniare.

h2. Exemplu

2.0 6.0
4.0 2.0
4.0 4.0

| 16.0000

| 16.0

|
h3. Explicaţie
Poligonul ales este $(2.0,0.0), (0.0 2.0), (0.0 4.0), (2.0 6.0), (4.0 4.0), (4.0,2.0)$ si are aria 16.

h2. Indicatii de rezolvare
 
Acest poligon se mai numeste si infasuratoarea convexa a punctelor.
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 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.
O alta solutie se poate
 

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