Problem F
Næstbest

Verið er að áætla hvað nemendur eru lengi að labba milli kennslustofa svo hægt sé að gefa mátulega mikinn tíma til þess í stundatöflu. Á fyrri forritunarkeppni voru keppendur fengnir til að meta hvert versta tilfellið væri, svo ekki þarf að gera það aftur. Nú er spurningin hvað bestu tilfellin séu. Verk þitt er því að finna hvað er langt milli þeirra tveggja bygginga sem eru næstar hvor annarri og hvað er langt milli þeirra tveggja bygginga sem eru næst næstar hvor annarri.

Inntak

Inntakið byrjar á einni línu með heiltölu $3\le n\le {10}^5$, fjöldi bygginga. Næst koma $n$ línur, hver með tveimur fleytitölum $-{10}^9\le x,y\le {10}^9$ sem gefa $x$ og $y$ hnit inngangsins að byggingu. Til einföldunar má gera ráð fyrir að nemendur labbi milli þessarra innganga eftir beinni loftlínu. Fleytitölurnar eru gefnar með mest $6$ aukastöfum.

Úttak

Prenta skal tvær línur. Á þá fyrri skal prenta hvað er langt milli bygginganna sem eru næstar hvor annarri. Á þá seinni skal prenta hvað er langt milli bygginganna sem eru næst næstar hvor annarri. Svar telst rétt ef bein eða hlutfallsleg skekkja þess frá réttu svari er mest ${10}^{-6}$.

5
0.0 0.0
1.0 2.0
2.0 2.0
3.0 0.0
3.0 3.0

1.0000000000
1.4142135624

5
1.0 0.0
0.0 1.0
1.0 1.0
2.0 1.0
1.0 2.0

1.0000000000
1.0000000000