Fişierul intrare/ieşire:popandai2.in, popandai2.outSursăGrigore Moisil By Net 2006
AutorCosmin Silvestru NegruseriAdăugată de
Timp execuţie pe test0.15 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

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.inpopandai2.outFigura
7
3 2
6 1
9 3
8 7
6 9
3 8
2 4
28.5
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content