問題概要
太郎君と二郎君は、無線機を使って会話をしています。
二人が使用している無線機は、電波を使ってお互いに直接通信し、 1kmの距離まで会話をすることができます。 またそれ以外にも、中継局を1つ以上間に挟むことで通信距離を延長することもできます。
無線機と中継局の間は、1km以内までしか通信できませんが、 中継局と中継局の間は、10km以内まで通信することができます。 (それぞれ1kmちょうど、10kmちょうどを含みます。)
2次元平面上に N本の中継局が立っており、 その位置は $Xi,Yi (1≤i≤N)$で表されます。
太郎君と二郎君はこれらの中継局をすべて自由に使用することができ、 また、太郎君と二郎君は無線機を持って2次元平面上を自由に移動できるとするとき、 太郎君と二郎君が、「直接」または「中継局を用いて間接的に」会話ができる 太郎君と二郎君の直線距離(ユークリッド距離)の最大を求めてください。
$N\leqq10^3$、$|p(x,y)|\leqq10^3$
解法
$N$が小さいのでUnionFindで通信可能なグループをまとめて、その中で直線距離の最大を求めれば良い。 答えの最小は2
計算量:$O(N^2)$