Fişierul intrare/ieşire:	infasuratoare.in, infasuratoare.out	Sursă	Arhiva educationala
Autor	Arhiva Educationala	Adăugată de	dragus marius •mariusdrg
Timp execuţie pe test	0.25 sec	Limită de memorie	24096 kbytes
Scorul tău	N/A	Dificultate	N/A

Poti vedea testele pentru aceasta problema accesand atasamentele.

Vezi solutiile trimise | Statistici

Infasuratoare convexa

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 de intrare

În fişierul de intrare infasuratoare.in se va gasi pe prima linie N, care reprezinta numarul de puncte. Pe urmatoarele N linii se vor gasi doua numere rationale X_i, Y_i care reprezinta coordonatele punctului i.

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.

Restricţii

• -1.000.000.000 ≤ X_i,Y_i ≤ 1.000.000.000
• Pentru 20% din teste N ≤ 20
• 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.

Exemplu

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.

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²) pasi. Aceast algoritm se numeste Jarvis March. O sursa se poate vedea aici.
O alta solutie se poate 

Cum se trimit solutii?