| Fişierul intrare/ieşire: | popandai2.in, popandai2.out | Sursă | Grigore Moisil By Net 2006 |
| Autor | Cosmin Silvestru Negruseri | Adăugată de | |
| Timp execuţie pe test | 0.075 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate |   3/5 |
Vezi solutiile trimise | Statistici
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.
Cerinta
Ajutati popandaii sa determine zona de arie maxima care satisface conditiile de mai sus!
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 (Xi , Yi) (separate printr-un spatiu) reprezentand coordonatele celei de-a i-a vizuina. Aceste coordonate vor fi date in ordine trigonometrica.
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.
Restrictii si precizari
- 4 ≤ N ≤ 1.000
- 1 ≤ Xi, Yi ≤ 30.000
- Pentru 60% din punctaj rezolvati problema pe cazul 3 ≤ N ≤ 300
Exemplu
| popandai2.in | popandai2.out | Figura |
|---|---|---|
| 7 3 2 6 1 9 3 8 7 6 9 3 8 2 4 | 28.5 |  |
