| Fişierul intrare/ieşire: | poligon3.in, poligon3.out | Sursă | Summer Challenge 2009, Runda 3 |
| Autor | Din Folclor | Adăugată de |  Paul-Dan Baltescu •pauldb |
| Timp execuţie pe test | 0.2 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Poligon3
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.
Date de intrare
Fişierul de intrare poligon3.in conţine pe prima linie numărul întreg N. Pe următoarele N linii se găsesc câte două numere întregi x şi y reprezentând coordonatele punctelor.
Date de ieşire
Î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.
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.
Exemplu
| poligon3.in | poligon3.out |
|---|---|
| 6 1 0 -2 3 0 -2 -5 -2 -3 -1 -3 3 | 13.00 |
Explicaţie
Cele 5 puncte care formează poligonul convex de arie maximă, în ordine trigonometrică, sunt: 3, 1, 2, 6, 5.
Trebuie sa te autentifici pentru a trimite solutii. Click aici
remote content
