== include(page="template/taskheader" task_id="adapost") ==
==Include(page="template/taskheader" task_id="adapost")==
Poveste ...
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. Restrictii
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 intrare
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. Date de iesire
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
h2. Exemplu:
| adapost.in | adapost.out |
| linia1
linia2
linia3
| linia1
linia2
|
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") ==
==Include(page="template/taskfooter" task_id="adapost")==
