==Include(page="template/taskheader" task_id="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.
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.
h2. Cerinta
Ajutatii pe popandai sa determine zona de arie minima care satisface conditiile de mai sus!
Ajutati-i pe popandai sa determine zona de arie minima care satisface conditiile de mai sus!
h2. Date de Intrare (fisier: popandai.in)
h2. 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.
Fisierul $popandai.in$ va contine pe prima linie numerele intregi $N$ si $K$. Urmatoarele $N$ linii vor contine cate doi intregi $x{~i~}, y{~i~}$ separati printr-un spatiu ce reprezinta coordonatele unei vizuine.
h2. Date de Iesire (fisier: popandai.out)
h2. Date de Iesire
Pe prima linie din fisierul de iesire se va gasi un singur numar real reprezentand aria minima a patrulaterului cautat. .
Pe prima linie din fisierul de iesire $popandai.out$ se va gasi un singur numar real reprezentand aria minima a patrulaterului cautat. .
h2. 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).
* $0 ≤ K ≤ N ≤ 300$
* $0 ≤ x{~i~}, y{~i~} ≤ 30000$
* nu exista $3$ puncte coliniare
* solutia se va afisa cu exact o zecimala
* va exista intotdeauna solutie ({$k + 3 < n$})
h2. Exemplu
table(example). |_. 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
| !problema/popandai?popandai.gif! |
h3. Explicatie
Poligonul de arie minima e format din varfurile $(7,2), (9, 6), (8,3)$ si $(8,1)$.
==Include(page="template/taskfooter" task_id="popandai")==
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
==Include(page="template/taskfooter" task_id="popandai")==
