== include(page="template/taskheader" task_id="insula2") ==
Î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ă.
Î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
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.
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
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ă.
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
* $... ≤ ... ≤ ...$
* $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
h3. Explicaţie
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
!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") ==
