Fişierul intrare/ieşire:adapost.in, adapost.outSursăinfo-arena 1.0
AutorMihai CiucuAdăugată de
Timp execuţie pe test0.65 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

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.

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.

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.

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.

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

Exemplu:

adapost.inadapost.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
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content