== include(page="template/taskheader" task_id="insula2") ==
Poveste şi cerinţă...
În jurul secolului al $XIV$-lea, cele $N$ clădiri aflate în Târgul Ieşilor puteau fi privite ca nişte puncte aparţinând primului cadran al unui sistem cartezian, în care axele erau reprezentate de cursul râului Bahlui. Acesta era împărţit în două sectoare: Bahluiul de Sus (reprezentat de semidreapta $OY$) şi Bahluiul de Jos (reprezentat de semidreapta $OX$). În acea perioadă mai-marii oraşului credeau că ar putea atrage mai mulţi turişti dacă ar transforma oraşul într-o insulă, prin construirea unui nou curs secundar. Aceştia trebuiau să ţină cont şi de dorinţele locuitorilor, care voiau să se traseze câte un drum orizontal (paralel cu Bahluiul de Jos) care să pornească din fiecare clădire până la malul nou construit al râului.
Construirea insulei se putea realiza prin desprinderea unui curs secundar, care să pornească din Bahluiul de Sus şi să se verse în Bahluiul de Jos, astfel încât toate clădirile oraşului să rămână în interiorul acestei insule nou formate sau exact pe marginea râului. În ideea de a păstra frumuseţea cadrului natural specific acestei zone, insula trebuia să aibă forma unui poligon convex, iar noul curs (cel secundar) să fie format din maximum $K$ laturi. Deasemenea, ştiindu-se că Bahluiul curge de la Nord la Sud, se dorea păstrarea acestui sens (parcurgând punctele cursului secundar de la intersecţia cu $OY$ către cea cu $OX$, ordonatele acestor puncte trebuiau să fie strict descrescătoare).
Ca şi în zilele noastre, mai-marii oraşului făceau doar promisiuni. Vi se cere vouă să aflaţi cum ar fi trebuit să fie construită insula astfel încât suma tuturor drumurilor cerute de localnici să fie minimă.
h2. Date de intrare
Fişierul de intrare $insula2.in$ ...
Pe prima linie a fişierului $insula2.in$ se găsesc două numere naturale $N$ şi $K$ separate prin câte un spaţiu, având semnificaţia din enunţ. Pe fiecare din următoarele $N$ linii se află câte două numere reale $X$ si $Y$ reprezentând coordonatele clădirilor.
h2. Date de ieşire
În fişierul de ieşire $insula2.out$ ...
Fişierul de ieşire $insula2.out$ conţine o singură linie pe care se află un singur număr real, reprezentând suma minimă cerută.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 300$
* $1 ≤ K ≤ 300$
* $1 ≤ X, Y ≤ 1 000 000$
* pentru $15%$ din teste $N = K$
* pentru alte $20%$ din teste, $N$, $K ≤ 16$
* pentru încă 25% $N$, $K ≤ 70$
* se consideră corectă orice sumă care diferă cu cel mult $0.0001$ faţă de rezultatul corect
h2. Exemplu
table(example). |_. insula2.in |_. insula2.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|4 2
1 2
3 4
2 5
1 3
|1.75
|
h3. Explicaţie
...
!problema/insula2?insula2.png!
Cursul secundar este format din cele două laturi îngroşate. Reamintind că distanţa este drumul orizontal, paralel cu axa $OX$, cele $4$ puncte se găsesc la distanţele $0.5$ (punctul $1$), $0$ (punctul $2$), $0$ (punctul $3$) şi $1.25$ (punctul $4$) de cursul secundar. Suma distanţelor este deci $1.75$.
== include(page="template/taskfooter" task_id="insula2") ==
