popandai

Popandai

== include(page="template/taskheader" task_id="popandai") ==

==Include(page="template/taskheader" task_id="popandai")==

Poveste ...

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

...

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

h2. Restrictii

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 $x{~i~}, y{~i~}$ separati printr-un spatiu ce reprezinta coordonatele unei vizuine.

h2. Date de intrare

h2. 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. .

h2. Date de iesire

h2. Restrictii

...

* $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

| popandai.in | popandai.out |
| linia1
linia2
linia3
| linia1
linia2
|

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")==
 

== include(page="template/taskfooter" task_id="popandai") ==

850