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

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.
• Oricare 3 puncte nu vor fi coliniare.

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.

Cum se trimit solutii?