poligon3

Poligon 3

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

Se dau $N$ puncte în plan. Să se determine poligonul de arie maximă având vârfurile în unele din cele $N$ puncte şi care nu conţine în interior nici unul din punctele date.

Se dau $N$ puncte în plan. Să se determine poligonul *convex* de arie maximă având vârfurile în unele din cele $N$ puncte şi care nu conţine în interior nici unul din punctele date.

h2. Date de intrare

h2. Date de ieşire

În fişierul de ieşire $poligon3.out$ se va afla un singur număr ce reprezintă aria maximă a unui poligon ce respectă cerinţa.

În fişierul de ieşire $poligon3.out$ se va afla un singur număr real cu minim două zecimale ce reprezintă aria maximă a unui poligon ce respectă cerinţa.

h2. Restricţii
* $1 ≤ N ≤ 500$
* $-15 000 ≤ x, y ≤ 15 000$
* Nu vor exista $3$ puncte colineare.

* O soluţie va fi considerată corectă dacă diferă prin maxim $0.01$ faţă de rezultatul corect.

* Pentru $20%$ din teste, $N ≤ 15$.
* Pentru $50%$ din teste, $N ≤ 100$.
h2. Exemplu
table(example). |_. poligon3.in |_. poligon3.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|

| 6
1 0
-2 3
0 -2
-5 -2
-3 -1
-3 3
| 13.00
|

h3. Explicaţie

...

Cele $5$ puncte care formează poligonul convex de arie maximă, în ordine trigonometrică, sunt: $3, 1, 2, 6, 5$.

== include(page="template/taskfooter" task_id="poligon3") ==

4083