Asa cum probabil ati ghicit,
este vorba despre o pasune obisnuita, cu o multime de flori împrastiate
pe suprafata ei.
Albinutele industriale zboara printre flori, aterizeaza pe flori si culeg polen
pentru a produce mierea. Întrucât viata si prosperitatea întregii
comunitati depinde de aceasta, fiecare floare trebuie sa fie vizitata, pentru
a aduna cât mai mult polen posibil.
Maya este albinuta care planifica modul în care albinutele industriale
viziteaza toate florile. O planificare consta dintr-o succesiune de multimi
de flori (de pozitii de flori, mai exact). Fiecare albinuta primeste o multime
de flori si trebuie sa viziteze toate florile din multimea respectiva, într-o
ordine arbitrara. Orice floare poate fi vizitata o data sau de mai multe ori.
O albinuta care primeste o multime de flori trebuie sa îsi planifice zborul,
alegând o ordine de vizitare a florilor care sa aiba cost minim si vizitând
apoi florile în aceasta ordine. Pentru o ordine de vizitare a florilor
data, definim costul ca fiind distanta maxima dintre doua flori vizitate consecutiv.
Deci costul unei multimi de flori este costul obtinut atunci cand albina viziteaza
florile in ordinea de cost minim. Costul unei planificari este costul maxim
al tuturor multimilor din planificare.
Cerinta
Scrieti un program care sa
o ajute pe Maya sa determine o planificare de cost minim.
Date
de intrare
Fisierul de intrare pasune.in
contine pe prima linie doua numere naturale separate prin spatiu F
B (F reprezinta numarul
de flori, iar B reprezinta numarul
de albine care culeg polen). Fiecare dintre urmatoarele F
linii contine câte doua numere naturale separate prin spatiu X
Y (pe linia i+1, X
este abscisa, iar Y este ordonata
celei de a i-a flori).
Date de iesire
Fisierul de iesire pasune.out
contine o singura linie pe care se afla costul minim al unei planificari, rotunjit
la doua zecimale.
Restrictii
1 <= F <= 2000
1 <= B <= F
1 <= X, Y <= 10000
Eroarea admisa este de 0.01
(cu alte cuvinte diferenta dintre rezultatul corect si rezultatul din fisierul
de iesire nu trebuie sa depaseasca 0.01).
Exemple
pasune.in
pasune.out
pasune.in
pasune.out
pasune.in
pasune.out
3
2
1 1
2 3
3 2
1.41
5 3
1 1
1 4
1 5
5 1
5 5
3.00
7 4
1 1
3 9
9 4
2 2
6 4
5 5
6 9
3.00
prof. Emanuela Cerchez
Liceul de Informatica "Grigore Moisil" Iasi
Contact:ema at mail.dntis.ro