問題一覧 > 通常問題

No.483 Arranging Matches

レベル : / AI推定難易度 : 1125 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 116
作問者 : mayoko_ / テスター : 🍡yurahuna
お気に入りにしたユーザー ProblemId : 689 / 自分の提出
問題文最終更新日: 2026-06-25 13:15:40
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 156 (順位表) の他の問題:

Problem Statement


Mayoko is playing a game of arranging matchsticks on a table. The table is a rectangle whose vertical and horizontal lengths are each 111 cm, and the coordinates of the point $r$cm vertically and $c$cm horizontally away from the top-left corner of the table are written as ($r, c$).

Mayoko has many matchsticks, each of length 1cm. She places each matchstick so that one of its endpoints is at coordinates ($r_0, c_0$) and the other endpoint is at coordinates ($r_1, c_1$). Here, $r_0, c_0, r_1, c_1$ are integers and satisfy $|r_1-r_0| + |c_1-c_0| = 1$.

A matchstick has a part called the "match head", which ignites when struck. Mayoko wants to arrange the matches so that no two or more match heads overlap at the same coordinates.

Given a list of places to put the matchsticks, determine whether the matchsticks can be placed so as to satisfy the above condition.

Input

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


The first line contains the number of matchsticks to be arranged, $N$. $1 \leq N \leq 100$
Each of the $N$ lines starting from the second line contains the information on the coordinates where a matchstick is placed, $r_0, c_0, r_1, c_1$, separated by spaces.
$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$ or $c_0 < c_1$
When $i \neq j$, $(r_{0i}, c_{0i}, r_{1i}, c_{1i}) \neq (r_{0j}, c_{0j}, r_{1j}, c_{1j})$

Output


Output "YES" (without the double quotes) if the $N$ matchsticks can be arranged as in the list given in the input so as to satisfy the condition, and "NO" (without the double quotes) if it is impossible to arrange them. Print a newline at the end.

Sample

Sample 1
Input
2
1 1 2 1
2 1 3 1
Output
YES



(The figures are borrowed from this problem.)
If the matches are placed as in the figure below, no two or more match heads (the red parts in the figure) overlap at the same coordinates.

Sample 2
Input
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
Output
NO


For example, if they are placed as in the figure below, two match heads overlap at each of the coordinates (1, 1) and (2, 1). With any other arrangement as well, match heads overlap at at least one coordinate, so output "NO".

Sample 3
Input
2
1 1 2 1
50 50 51 50
Output
YES


When the list of places to put the matchsticks is viewed as a graph, it may be disconnected.

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