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

==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.
 
h2. Cerinta
 
Ajutati popandaii sa determine zona de arie maxima care satisface conditiile de mai sus!
 
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 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.
 
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$
 
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! |
 
==Include(page="template/taskfooter" task_id="popandai2")==
 
 

==Include(page="template/raw")==
 
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.
 
h2. Cerinta
 
Ajutati popandaii sa determine zona de arie maxima care satisface conditiile de mai sus!
 
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.
 
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.
 
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.
 
h2. Exemplu
 
 
|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")==

972