20319번 - Drugi Dio 스페셜 저지다국어

Naš omiljeni vodič shvatio je da je u prvom dijelu izvedena spačka koja je uništila njegove šanse za pobjedu. Poražen, posramljen i prašnjav, vodič je skovao plan za osvetu. Ovaj put je prednost domaćeg terena na njegovoj strani, a gospodin Malnar naizgled nema šanse. Naime, radi se o utrci! Nije to utrka na 100 metara ili neki pišljivi maraton, ovo je epska utrka između dvaju gradova u zemlji vatre. Jedino pravlio je da nema pravila, a sve što je važno jest stići iz polazišnog grada u odredišni grad prije suparnika.

Vodič se odlučio utrkivati biciklom jer zna da su trenutno zatvorene sve međugradske prometnice za automobile. Budući da zna da gospodin Malnar nije svjestan te činjenice te se smatra fizički nadmoćnijim, dopustit će mu da sam odabere između kojih će se gradova utrkivati.

Međutim, vodič ne zna da je gospodin Malnar ionako već unajmio privatni helikopter u slučaju da treba obaviti neke stvari na drugom kraju grada. Naravno, gospodin Malnar je prihvatio izazov, ali se i malo sažalio nad jadnim vodičem pa je odlučio odabrati rutu u kojoj će pobijediti s najmanjom mogućom prednosti.

Gradovi u Azerbajdžanu mogu se prikazati kao točke u koordinatnom sustavu. Međugradske biciklističke staze poprimaju oblik pravokutne mreže pa se vodič može kretati samo usporedno s koordinatnim osima. S druge pak strane, gospodin Malnar će se između gradova kretati dužinom koja ih spaja. Preciznije, ako se početni grad nalazi u točki (x₁, y₁), a završni se nalazi u točki (x₂, y₂), vodič će prevaliti udaljenost d_v = |x₁ − x₂| + |y₁ − y₂|, dok će gospodin Malnar prevaliti udaljenost d_m = √((x₁ − x₂)² + (y₁ − y₂)²). Gospodin Malnar će odabrati par gradova za koje je omjer d_v/d_m najmanji mogući. Odredite taj omjer!

U prvom je retku prirodan broj n (2 ≤ n ≤ 300 000) iz teksta zadatka.

U i-tom od sljedećih n redaka nalaze se cijeli brojevi x_i, y_i (0 ≤ |x_i|, |y_i| ≤ 10⁹) koji predstavljaju koordinate i-tog grada. Niti jedna dva grada neće se nalaziti na istim koordinatama.

U prvom je retku potrebno ispisati traženi omjer iz teksta zadatka.

Tolerirat će se apsolutno ili relativno odstupanje od službenog rješenja za 10⁻¹⁰.