圏外です。(EASY) [yukicoder 94] - はまやんはまやんはまやん

問題

N個の中継局がある。
無線機間、無線機と中継局の間は1km以内なら通信できる。
中継局間は10km以内なら通信できる。
中継局の座標が整数で与えられているとき、太郎君と二郎君が通信できる最大距離（ユークリッド距離）は？

　0 <= N <= 10^3
　-10^3 <= Xi,Yi <= 10^3

考察

1. 幾何っぽいので小さいケースから実験を始めていく

N=0 : 通信局は無いため、互いに通信するしかないので、1km
N=1 : 通信局を1つ使うため、1+1=2km
N=2 : これは場合分けが必要。
　2つの通信局間で通信可能でないなら、N=1と状況は変わらないので、2km
　通信可能であれば、2つの中継局を直線で結んだ延長上に二人が立つことにより、((その2点の距離)+2)km
　これはサンプル1で示されている

ここで重要な考察、ある2つの中継局が通信可能なら((その2点の距離)+2)が通信可能な最大距離になる
これさえ出せればそんなに難しい問題じゃない

2. 必要なことは「ある2つの中継局が通信可能かどうか」を判別すること
3. 中継局を点、ある2点間の距離が10km以下であれば、その間に辺があると考えれば、通信可能は連結であることに言い換えられる
4. ある2点間が連結であることを高速に判定するアルゴリズム -> UnionFind
5. 誤差が怖いので、「(2点間の距離)<=10」ではなく「(2点間の距離)^2<=100」とすれば整数比較ができ、誤差が出ない

6. 最後に全ての通信可能な2点間に対し、((その2点の距離)+2)の最大をとればよい

実装

http://yukicoder.me/submissions/102747

template<int um> class UF { // from kmjp
public:
	vector<int> par;
	UF() { par = vector<int>(um, 0); rep(i, 0, um) par[i] = i; }
	int operator[](int x) { return par[x] == x ? x : par[x] = operator[](par[x]); }
	void operator()(int x, int y)
	{
		x = operator[](x); y = operator[](y);
		if (x != y) par[x] = y;
	}
};
//-----------------------------------------------------------------
int N;
int X[1010], Y[1010];
//-----------------------------------------------------------------
int main()
{
	cin >> N;
	rep(i, 0, N) scanf("%d %d", &X[i], &Y[i]);

	if (N == 0) {
		printf("1\n");
		return 0;
	}

	UF<1010> uf;
	rep(i, 0, N) rep(j, i + 1, N) {
		int dd = (X[i] - X[j]) * (X[i] - X[j]) + (Y[i] - Y[j]) * (Y[i] - Y[j]);
		if (dd <= 100) {
			uf(i, j);
		}
	}

	double ans = 0;
	rep(i, 0, N) rep(j, 0, N) if (uf[i] == uf[j]) {
		int dd = (X[i] - X[j]) * (X[i] - X[j]) + (Y[i] - Y[j]) * (Y[i] - Y[j]);
		double d = sqrt(dd);
		ans = max(ans, d + 2.0f);
	}
	printf("%.10f\n", ans);
}