通信強度 C#編（paizaランク S 相当）

問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！

問題

下記の問題をプログラミングしてみよう！

n 個の点の座標 (x_i, y_i) と通信強度 a_i が与えられます。
各点 (x_i, y_i) は、チェビシェフ距離が a_i 以内の点にデータを送信できます。
データを受信した点は、そのデータを別の点に送信することができます。

ここで、2 つの点 p, q の間でデータの送信が可能であるとは、p から 0 個以上の点を経由して q にデータを送信できることを指します。
このとき、すべての点の間でデータの送信が可能かどうかを判定してください。

なお、点 (x_1, y_1) と点 (x_2, y_2) のチェビシェフ距離は max(|x_1 - x_2|, |y_1 - y_2|) で表されます。

入力される値

n
x_1 y_1 a_1
x_2 y_2 a_2
...
x_n y_n a_n

・ 1 行目に、点の数を表す整数 n が与えられます。
・続く n 行 (1 ≦ i ≦ n) に、点の座標 x_i, y_i と通信強度 a_i が半角スペース区切りで与えられます。

入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。標準入力からの値取得方法はこちらをご確認ください

期待する出力: すべての点の間でデータの送信が可能である場合は "Yes"、そうでない場合は "No" と出力してください。

出力の最後に改行を入れ、余計な文字、空行を含んではいけません。

条件: すべてのテストケースにおいて、以下の条件を満たします。

・ 1 ≦ n ≦ 1000 = 10^3
・ 0 ≦ x_i, y_i, a_i ≦ 1000
・ x_i ≠ x_j または y_i ≠ y_j (1 ≦ i < j ≦ n)

入力例1: 2
0 0 0
1 1 1

出力例1: No

入力例2: 16
2 2 2
2 7 2
7 2 2
7 7 2
2 3 1
2 4 1
2 5 1
4 2 1
5 2 1
6 2 1
3 7 1
4 7 1
5 7 1
7 4 1
7 5 1
7 6 1

出力例2: Yes

問題一覧へ戻る