| Fişierul intrare/ieşire: | insula2.in, insula2.out | Sursă | ONI 2012 - Baraj |
| Autor | Alexandru Cazacu | Adăugată de |  Eugenie Daniel Posdarascu •eudanip |
| Timp execuţie pe test | 0.2 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
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ă.
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.
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ă.
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
Exemplu
| insula2.in | insula2.out |
|---|---|
| 4 2 1 2 3 4 2 5 1 3 | 1.75 |
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.
