Revizia anterioară Revizia următoare
| 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
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.in | popandai.out | Figura |
|---|---|---|
| 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).
