popandai2

Popandai2

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

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

Poveste ...

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. Restrictii

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 intrare

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. Date de iesire

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 |
| linia1
linia2
linia3
| linia1
linia2
|

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/taskfooter" task_id="popandai2") ==

972