問題
太郎君と二郎君は、無線機を使って会話をしています。
二人が使用している無線機は、電波を使ってお互いに直接通信し、1kmの距離まで会話をすることができます。
またそれ以外にも、中継局を1つ以上間に挟むことで通信距離を延長することもできます。
無線機と中継局の間は、1km以内までしか通信できませんが、中継局と中継局の間は、10km以内まで通信することができます。
(それぞれ1kmちょうど、10kmちょうどを含みます。)
2次元平面上に N本の中継局が立っており、その位置は Xi,Yi (1≤i≤N)で表されます。
太郎君と二郎君はこれらの中継局をすべて自由に使用することができ、また、太郎君と二郎君は無線機を持って2次元平面上を自由に移動できるとするとき、太郎君と二郎君が、「直接」または「中継局を用いて間接的に」会話ができる
太郎君と二郎君の直線距離(ユークリッド距離)の最大を求めてください。
入力
N X1 Y1 X2 Y2 … Xi Yi … XN YN
1行目に、中継局の数を表す整数 N (0≤N≤1000) が与えられます。 2本の中継局の間は√85kmなので、通信可能範囲です。 2本の中継局の間は約10.6kmなので、通信できません。 中継局が存在しないときは、直接通信しなければなりません。
続くN行に、各中継局の位置を表す整数のペアXi,Yi (−1000≤Xi,Yi≤1000,1≤i≤N)がスペース区切りで与えられます。(単位[km])
同一の座標に複数の中継局が存在することはありません。
出力
太郎君と二郎君が会話をすることができる直線距離の最大を出力してください。
誤差は絶対誤差あるいは相対誤差の少なくとも片方が 10−6 以下であれば許容されます。
最後に改行してください。
入出力例
入力例1
2
3 3
12 1
出力例1
11.219544457
さらに太郎君と中継局の間は1km、二郎君と中継局の間も1kmまで通信できるため、
2本の中継局を直線で結んだ延長上に二人が立つことにより、
((√85)+2)kmまで通信可能となります。
入力例2
2
-5 -1
3 6
出力例2
2
この場合どちらか1本の中継局を挟み、太郎君と中継局の間は1km、
二郎君と中継局の間も1kmまで通信できるため、2kmが解となります。
入力例3
5
-8 7
-5 -1
3 5
9 -3
16 4
出力例3
26.186773244
入力例4
0
出力例4
1
この場合、お互いに電波が届く範囲の1kmが最大距離になります。