No.483 マッチ並べ

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 64
作問者 : mayoko_mayoko_ / テスター : 🍡yurahuna🍡yurahuna

5 ProblemId : 689 / 出題時の順位表

問題文


真横さんは, テーブルの上にマッチ棒を並べる遊びをしています。テーブルは縦, 横の長さがそれぞれ 111 cm の長方形の形をしていて, テーブルの左上から縦に $r$cm, 横に$c$cm 離れた座標を($r, c$) と表すことにします。

真横さんは一本の長さが 1cm のマッチ棒をたくさん持っています。真横さんはこのマッチ棒を, 一方の端点の座標が($r_0, c_0$), もう一方の端点の座標が($r_1, c_1$) になるように置いていきます。ただし, $r_0, c_0, r_1, c_1$ は整数で, $|r_1-r_0| + |c_1-c_0| = 1$ を満たします。

ところで, マッチ棒には「頭薬」と言う, シュッとやると燃える部分があります。真横さんは, この頭薬が同じ座標に 2 つ以上重なることが無いようにマッチを並べたいと考えています。

マッチ棒を置く場所のリストが与えられるので, 上の条件を満たすようにマッチ棒を置けるか判定して下さい。

入力

$N$
$r_{01} c_{01} r_{11} c_{11}$
...
$r_{0N} c_{0N} r_{1N} c_{1N}$


1 行目には, 並べたいマッチ棒の本数 $N$ が与えられます。 $1 \leq N \leq 100$
2 行目からの $N$ 行にはマッチ棒の置かれる座標に関する情報 $r_0, c_0, r_1, c_1$ が空白区切りで与えられます。
$1 \leq r_0, c_0, r_1, c_1 \leq 100$
$|r_1-r_0| + |c_1-c_0| = 1$
$r_0 < r_1$ または $c_0 < c_1$
$i \neq j$ の時, $(r_{0i}, c_{0i}, r_{1i}, c_{1i}) \neq (r_{0j}, c_{0j}, r_{1j}, c_{1j})$

出力


入力で与えられたリストの通りに, $N$ 本のマッチ棒を条件を満たすように並べることが出来る場合は "YES" (ダブルクオーテーションは不要)を, 並べることが不可能な場合は "NO" (ダブルクオーテーションは不要) を出力して下さい。最後に改行して下さい。

サンプル

サンプル1
入力
2
1 1 2 1
2 1 3 1
出力
YES



(図は この問題 の図をお借りしています)
下図のようにマッチを配置すれば, 頭薬(図の赤いやつ)が同じ座標に 2 つ以上重なることはありません。

サンプル2
入力
7
1 1 2 1
1 1 1 2
1 2 2 2
2 1 2 2
2 1 3 1
2 2 3 2
3 1 3 2
出力
NO


例えば下図のように配置すると, 座標(1, 1), (2, 1) で頭薬が 2 つ重なってしまっています。他のどのような並べ方をしても少なくともひとつの座標で頭薬は重なってしまうので, "NO" を出力します。

サンプル3
入力
2
1 1 2 1
50 50 51 50
出力
YES


マッチ棒を置く場所のリストをグラフと見た時, 非連結になっていることがあります。

提出ページヘ