問題一覧 > 通常問題

No.96 圏外です。

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 小数誤差許容問題 絶対誤差または相対誤差が$10^{-6}$ 以下。ただし、ジャッジ側の都合で500桁未満にしてください
タグ : / 解いたユーザー数 58
作問者 : なおなお
3 ProblemId : 115 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2015-11-14 17:46:39

問題文

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

二人が使用している無線機は、電波を使ってお互いに直接通信し、
\(1km\)の距離まで会話をすることができます。
またそれ以外にも、中継局を\(1\)つ以上間に挟むことで通信距離を延長することもできます。

無線機と中継局の間は、\(1km\)以内までしか通信できませんが、
中継局と中継局の間は、\(10km\)以内まで通信することができます。
(それぞれ\(1km\)ちょうど、\(10km\)ちょうどを含みます。)

2次元平面上に \(N\)本の中継局が立っており、
その位置は \(X_i,Y_i\ (1 \leq i \leq N)\)で表されます。

太郎君と二郎君はこれらの中継局をすべて自由に使用することができ、
また、太郎君と二郎君は無線機を持って2次元平面上を自由に移動できるとするとき、
太郎君と二郎君が、「直接」または「中継局を用いて間接的に」会話ができる
太郎君と二郎君の直線距離(ユークリッド距離)の最大を求めてください。

入力

\(N\)
\(X_1\ Y_1\)
\(X_2\ Y_2\)
\(\dots\)
\(X_i\ Y_i\)
\(\dots\)
\(X_N\ Y_N\)

\(1\)行目に、中継局の数を表す整数 \(N\ (0 \leq N \leq 120000)\) が与えられます。
続く\(N\)行に、各中継局の位置を表す整数のペア\(X_i,Y_i\ (-10000 \leq X_i,Y_i \leq 10000, 1 \leq i \leq N)\)がスペース区切りで与えられます。(単位\([km]\))
同一の座標に複数の中継局が存在することはありません。
つまり $i \neq j $であれば$(X_i,Y_i) \neq (X_j,Y_j)$

出力

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

サンプル

サンプル1
入力
2
3 3
12 1
出力
11.219544457

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

サンプル2
入力
2
-5 -1
3 6
出力
2

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

サンプル3
入力
5
-8 7
-5 -1
3 5
9 -3
16 4
出力
26.186773244

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。