0533 - 圏外?

時間制限 1 秒 / メモリ制限 64 MB / 得点 1 / Writer ei1439 / x 2 / 統計 /

    タグ:

誤差
1e-6
TLE
1sec
MLE
64MB
得点
1

問題

太郎君と二郎君は、無線機を使って会話をしています。

二人が使用している無線機は、電波を使ってお互いに直接通信し、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) が与えられます。
続くN行に、各中継局の位置を表す整数のペアXi,Yi (−1000≤Xi,Yi≤1000,1≤i≤N)がスペース区切りで与えられます。(単位[km])
同一の座標に複数の中継局が存在することはありません。 つまり、i≠jであれば(Xi,Yi)≠(Xj,Yj)

出力

太郎君と二郎君が会話をすることができる直線距離の最大を出力してください。
誤差は絶対誤差あるいは相対誤差の少なくとも片方が 10−6 以下であれば許容されます。
最後に改行してください。

入出力例

入力例1

2
3 3
12 1

出力例1

11.219544457

2本の中継局の間は√85kmなので、通信可能範囲です。
さらに太郎君と中継局の間は1km、二郎君と中継局の間も1kmまで通信できるため、 2本の中継局を直線で結んだ延長上に二人が立つことにより、 ((√85)+2)kmまで通信可能となります。

入力例2

2
-5 -1
3 6

出力例2

2

2本の中継局の間は約10.6kmなので、通信できません。
この場合どちらか1本の中継局を挟み、太郎君と中継局の間は1km、 二郎君と中継局の間も1kmまで通信できるため、2kmが解となります。

入力例3

5
-8 7
-5 -1
3 5
9 -3
16 4

出力例3

26.186773244

入力例4

0

出力例4

1

中継局が存在しないときは、直接通信しなければなりません。
この場合、お互いに電波が届く範囲の1kmが最大距離になります。