Fişierul intrare/ieşire:popandai.in, popandai.outSursăpreONI 2006 Runda 4
AutorAdrian Vladu, Cosmin Silvestru NegruseriAdăugată de
Timp execuţie pe test2.5 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Popandai

Cei K popandai de pe tarlaua vesela vor sa se adaposteasca de vultur in cele N vizuine sapate in pamant. Tarlaua va fi planul euclidian, iar vizuinele vor fi puncte de coordonate intregi. Pentru a fi protejati de un atac al vulturului ei vor sa stabilesca o zona sigura in forma de patrulater, zona in care pot usor sa se avertizeze si sa se adaposteasca la aparitia vreunui vultur. Aceasta zona trebuie sa contina strict in interior cel putin K vizuine astfel ca fiecare popandau sa aiba vizuina lui. De asemenea varfurile zonei alese vor corespunde unor vizuine. Nu vor exista trei vizuine care sa fie coliniare.

Cerinta

Ajutati-i pe popandai sa determine zona de arie minima care satisface conditiile de mai sus!

Date de Intrare

Fisierul popandai.in va contine pe prima linie numerele intregi N si K. Urmatoarele N linii vor contine cate doi intregi xi, yi separati printr-un spatiu ce reprezinta coordonatele unei vizuine.

Date de Iesire

Pe prima linie din fisierul de iesire popandai.out se va gasi un singur numar real reprezentand aria minima a patrulaterului cautat. .

Restrictii

  • 0 ≤ K ≤ N ≤ 300
  • 0 ≤ xi, yi ≤ 30000
  • nu exista 3 puncte coliniare
  • solutia se va afisa cu exact o zecimala
  • va exista intotdeauna solutie (k + 3 < n)

Exemplu

popandai.inpopandai.outFigura
8 0
5 9
9 6
8 1
0 7
7 2
1 3
2 0
8 3
2.0

Explicatie

Poligonul de arie minima e format din varfurile (7,2), (9, 6), (8,3) si (8,1).

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content