Fişierul intrare/ieşire:	popandai.in, popandai.out	Sursă	preONI 2006 Runda 4
Autor	Adrian Vladu, Cosmin Silvestru Negruseri	Adăugată de
Timp execuţie pe test	1.25 sec	Limită de memorie	65536 kbytes
Scorul tău	N/A	Dificultate	5/5

Vezi solutiile trimise | Statistici

Popandai

Link: [1]File-List
Link: [2]Edit-Time-Data

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

Ajutatii pe popandai sa determine zona de arie minima care satisface conditiile de mai sus!

Date de Intrare (fisier: popandai.in)

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 (fisier: popandai.out)

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

Restrictii

S 0 <= k <= n <= 300

S 0 <= xi, yi <= 30000

S nu exista 3 puncte coliniare

S solutia se va afisa cu exact o zecimala

S va exista intotdeauna solutie (k + 3 < n)

popandai.in popandai.out Explicatie
8 0 2.0 Poligonul de arie minima e format
din varfurile (7,2), (9, 6), (8,3)
5 9 si (8,1).

9 6

8 1

0 7

7 2

1 3

2 0

8 3

References

Visible links
1. file:///home/eval/eval/www/infoarena/docs/arhiva/popandai/enunt_files/filelist.xml
2. file:///home/eval/eval/www/infoarena/docs/arhiva/popandai/enunt_files/editdata.mso

Cum se trimit solutii?