==Include(page="template/taskheader" task_id="popandai2")==

Popandaii de pe "tarlaua vesela"au scapat de atacul vulturilor si acum trebuie sa se adaposteasca de lupi in vizuinile lor. Aceste vizuini se pot identifica prin puncte avand coordonate intregi in plan si sunt dispuse in colturile unui poligon convex. Pentru a fi protejati de atacul lupilor, popandaii vor sa stabileasca un perimetru de siguranta cat mai mare posibil, unde se pot misca in voie. Acest perimetru va fi in forma de patrulater si va avea varfurile situate in patru din cele N puncte care reprezinta vizuinile.

Popandaii de pe "tarlaua vesela" au scapat de atacul vulturilor si acum trebuie sa se adaposteasca de lupi in vizuinile lor. Aceste vizuini se pot identifica prin puncte avand coordonate intregi in plan si sunt dispuse in colturile unui poligon convex. Pentru a fi protejati de atacul lupilor, popandaii vor sa stabileasca un perimetru de siguranta cat mai mare posibil, unde se pot misca in voie. Acest perimetru va fi in forma de patrulater si va avea varfurile situate in patru din cele $N$ puncte care reprezinta vizuinile.

h2. Cerinta

h2. Date de Intrare

Pe prima linie a fisierului de intrare popandai2.in se afla un numar intreg N , reprezentand numarul vizuinilor. Urmatoarele N linii contin fiecare cate doua numaere intregi ( X[i] , Y[i] ) (separate printr-un spatiu) reprezentand coordonatele celei de-a i -a vizuina. Aceste coordonate vor fi date in ordine trigonometrica.

Pe prima linie a fisierului de intrare $popandai2.in$ se afla un numar intreg $N$, reprezentand numarul vizuinilor. Urmatoarele $N$ linii contin fiecare cate doua numere intregi ({$X{~i~} , Y{~i~}$}) (separate printr-un spatiu) reprezentand coordonatele celei de-a {$i$}-a vizuina. Aceste coordonate vor fi date in ordine trigonometrica.

h2. Date de Iesire

Pe prima linie a fisierului de iesire popandai2.out va fi afisat un singur numar real cu o zecimala exacta reprezentand aria maxima a patrulaterului cautat.

Pe prima linie a fisierului de iesire $popandai2.out$ va fi afisat un singur numar real cu o zecimala exacta reprezentand aria maxima a patrulaterului cautat.

h2. Restrictii si precizari

. 4 <= N <= 1.000
 
. 1 <= X[i], Y[i] <= 30.000
 
. Pentru 60% din punctaj rezolvati problema pe cazul 3 <= N <= 300.

* $4 ≤ N ≤ 1.000$
* $1 ≤ X{~i~}, Y{~i~} ≤ 30.000$
* Pentru $60%$ din punctaj rezolvati problema pe cazul $3 ≤ N ≤ 300$

h2. Exemplu

table(example). |_. popandai2.in |_. popandai2.out |_. Figura |
| 7
3 2
6 1
9 3
8 7
6 9
3 8
2 4
| 28.5
| !problema/popandai2?popandai2.jpg! |

|popandai2.in |popandai2.out |
 
|7 |28.5 |
|3 2 | |
|6 1 | |
|9 3 | |
|8 7 | |
|6 9 | |
|3 8 | |
|2 4 | |
 

==Include(page="template/taskfooter" task_id="popandai2")==

==Include(page="template/taskfooter" task_id="popandai2")==

972