Županijsko natjecanje 2011. godine za 1. i 2. razred Srednje Škole - 4. zadatak

Informatička tvrtka HookMeUp je na javnom natječaju dobila posao umrežavanja važnih gradskih lokacija. Cilj im je provudi mrežne kabele koji de spajati sve lokacije. Dvije lokacije se smatraju spojenima ako među njima postoji direktna veza barem jednim kabelom ili postoji indirektna veza, odnosno niz drugih lokacija preko kojih su te dvije lokacije spojene.

S obzirom da tvrtka želi uštedjeti na iskopavanju kanala i postavljanju kabela, planiraju sagraditi takvu mrežu da ukupna cijena izgradnje cijele mreže bude što manja (cijena je proporcionalna dužini kabela), a da ipak sve lokacije budu spojene.

Grad je pristao na ovakav plan izgradnje, ali je od tvrtke HookMeUp zatražio da im dostavi informaciju o najvedoj mogudoj mrežnoj latenciji između bilo koje dvije lokacije u tako izgrađenoj mreži. Mrežna latencija je vrijeme potrebno da informacija stigne s jedne lokacije do druge. Latencija je proporcionalna ukupnoj dužini kabela u jednoj vezi (bilo direktnoj ili indirektnoj) između dviju spojenih lokacija, pa stoga tvrtku zanima kolika de biti najveda udaljenost između bilo koje dvije lokacije, tako da naknadno mogu izračunati stvarnu latenciju

ULAZNI PODACI

U prvom redu se nalazi prirodan broj N ( 1 ≤ N ≤ 500 ), koji predstavlja broj lokacija koje je potrebno spojiti. U sljededih N redova nalaze se po dva cijela broja X i Y ( -500 ≤ X, Y ≤ 500 ), koji predstavljaju koordinate i-te lokacije.

IZLAZNI PODACI

U prvom i jedinom retku potrebno je ispisati najvedu udaljenost između bilo koje dvije lokacije u gore spomenutoj mreži. Broj treba zaokružiti na dvije decimalne znamenke (čak i ako je rješenje cijeli broj, potrebno je ispisati decimalnu točku i potom dvije nule).

PRIMJERI TEST PODATAKA

ulaz

2
1 1
2 2

izlaz

1.41

ulaz

5
1 1
-2 6
4 6
1 2
3 6

izlaz

10.47

ulaz

9
-5 -3
-2 -1
-2 4
2 4
1 1
2 -3
3 3
3 1
7 2

izlaz

16.63

Objašnjenje

Objašnjenje trećeg test primjera: Tvrtka će izgraditi mrežu kao na slici, jer je njena cijena minimalna u odnosu na druge moguće mreže. Tada je najveća udaljenost od točke 3 do točke 1. Kada zbrojimo sve udaljenosti dobijemo: (3->4 = 4); (4->7 = 1.41); (7->8 = 2); (8->5 = 2); (5->2 = 3.61); (2->1 = 3.61) i konačno, dužina cijelog puta iznosi 16.63.