==Include(page="template/taskheader" task_id="adapost")==
 
==Include(page="template/raw")==
 
Adapost
 
 
 
 
 
Un batalion de N soldati a ajuns intr-o zona periculoasa si se afla sub un puternic bombardament din partea inamicului. Comandantul Gigel are o harta cu pozitiile soldatilor si coordonatele a N adaposturi, cu o capacitete de o persoana fiecare, la care trebuie sa ajunga soldatii. El doreste sa-si faca un plan de salvare a soldatilor care sa aiba un risc cat mai mic. Riscul unui soldat de a fi ranit este direct proportional cu timpul de care are nevoie sa ajunga la adapostul sau, deci este si direct proportional cu distanta parcursa de el, deoarece toti soldatii au viteza constanta.
 
Gigel doreste ca fiecare soldat sa aiba sanse cat mai bune, astfel incat maximul distantelor care trebuie parcurse de fiecare soldat pana la adapostul sau sa fie minim. Desi maximul distantelor trebuie sa fie cat mai mic, el mai vrea ca suma distantelor parcurse de soldati sa fie cat mai mica deasemenea, pentru a micsora riscul total.
 
h2. Cerinta
 
Alegeti pentru fiecare soldat un adapost, astfel incat in fiecare adapost sa fie un singur soldat si si ambele conditii de mai sus sa fie respectate.
 
h2. Date de Intrare
 
Prima linie a fisierului adapost.in contine un numar intreg N reprezentand numarul de soldati. Urmatoarele N linii contin coordonatele soldatilor iar urmatoarele N linii contin coordonatele adaposturilor.
 
h2. Date de Iesire
 
In fisierul adapost.out se vor scrie doua numere reale: valoarea maxima a distantelor soldat-adapost care satisface cerinta si suma minima a distantelor parcurse de soldati pana la adaposturile lor.
 
h2. Restrictii si precizari:
 
o 1 <= N <= 400
o Pentru aflarea primului numar se acorda 40% din valoarea unui test, restul de punctaj fiind acordat daca ambele numere sunt aflate.
o Este posibil ca suma distantelor soldat-adapost sa fie si mai mica decat cea cautata, dar in acea situatie maximul distantelor ar fi prea mare.
o Punctele au coordonate in intervalul [0,1000] si sunt date cu o precizie de 0,001
o Diferenta maxima cu care rezultatul final poate varia fata de cel corect este de 0,001
 
h2. Exemplu:
 
 
 
adapost.in adapost.out
5 4.07690 14.76992
 
6.773 5.394
 
1.981 1.198
 
7.062 7.228
 
2.247 5.785
 
6.749 2.419
 
5.382 7.861
 
5.414 3.397
 
8.789 3.838
 
9.436 1.929

==Include(page="template/taskheader" task_id="adapost")==
 
Un batalion de $N$ soldati a ajuns intr-o zona periculoasa si se afla sub un puternic bombardament din partea inamicului. Comandantul Gigel are o harta cu pozitiile soldatilor si coordonatele a $N$ adaposturi, cu o capacitete de o persoana fiecare, la care trebuie sa ajunga soldatii. El doreste sa-si faca un plan de salvare a soldatilor care sa aiba un risc cat mai mic. Riscul unui soldat de a fi ranit este direct proportional cu timpul de care are nevoie sa ajunga la adapostul sau, deci este si direct proportional cu distanta parcursa de el, deoarece toti soldatii au viteza constanta.
 
Gigel doreste ca fiecare soldat sa aiba sanse cat mai bune, astfel incat maximul distantelor care trebuie parcurse de fiecare soldat pana la adapostul sau sa fie minim. Desi maximul distantelor trebuie sa fie cat mai mic, el mai vrea ca suma distantelor parcurse de soldati sa fie cat mai mica deasemenea, pentru a micsora riscul total.
 
h2. Cerinta
 
Alegeti pentru fiecare soldat un adapost, astfel incat in fiecare adapost sa fie un singur soldat si si ambele conditii de mai sus sa fie respectate.
 
h2. Date de Intrare
 
Prima linie a fisierului $adapost.in$ contine un numar intreg $N$ reprezentand numarul de soldati. Urmatoarele $N$ linii contin coordonatele soldatilor iar urmatoarele $N$ linii contin coordonatele adaposturilor.
 
h2. Date de Iesire
 
In fisierul $adapost.out$ se vor scrie doua numere reale: valoarea maxima a distantelor soldat-adapost care satisface cerinta si suma minima a distantelor parcurse de soldati pana la adaposturile lor.
 
h2. Restrictii si precizari:
 
* $1 ≤ N ≤ 400$
* Pentru aflarea primului numar se acorda $40%$ din valoarea unui test, restul de punctaj fiind acordat daca ambele numere sunt aflate.
* Este posibil ca suma distantelor soldat-adapost sa fie si mai mica decat cea cautata, dar in acea situatie maximul distantelor ar fi prea mare.
* Punctele au coordonate in intervalul $[0,1000]$ si sunt date cu o precizie de $0,001$
* Diferenta maxima cu care rezultatul final poate varia fata de cel corect este de $0,001$
 
h2. Exemplu:
 
table(example). |_. adapost.in |_. adapost.out |
| 5
6.773 5.394
1.981 1.198
7.062 7.228
2.247 5.785
6.749 2.419
5.382 7.861
5.414 3.397
8.789 3.838
9.436 1.929
5.550 7.901
| 4.07690 14.76992 |
 
==Include(page="template/taskfooter" task_id="adapost")==

5.550 7.901
==Include(page="template/taskfooter" task_id="adapost")==

663