008 - ラボライブ　タフグローバルフェスティバル

問題

背景

音楽ゲームが好きなビッグブリッジ伯爵は、ある音楽ゲームをクリアしたいと思っている。 幸いにも、そのゲームにおいて、どのタイミングでどこをタッチすればよいのかは分かっているが、ビッグブリッジ伯爵には自分のスキルで実際にクリアすることができるかどうかがわからない。 そこであなたは、ビッグブリッジ伯爵がその音楽ゲームをクリアすることができるかどうかを調べてあげることにした。

課題

ビッグブリッジ伯爵が音楽ゲームで使うことのできる指の数 m と各指の初期位置 (rx_i, ry_i) が与えられる。 また、音楽ゲームにおいてタッチすべき場所とタイミングが n 個与えられる。 この音楽ゲームをクリアするためには、各 i (1 ≤ i ≤ n) に対して、2 次元平面上の (px_i, py_i) の位置をどれか 1 つ以上の指で時間 s_i から t_i の間、ずっとタッチし続ける必要がある。 さらに、この音楽ゲームでは各場所をタッチすべきタイミングが連続している。 つまり、各 i (1 ≤ i ≤ n - 1) に対して、t_i = s_i+1 となっている。 ビッグブリッジ伯爵はそれぞれの指を独立に、1 単位時間あたりユークリッド距離で最大 1 の速度で任意の方向に動かすことができる。 ビッグブリッジ伯爵がこの音楽ゲームをクリアすることができるかどうかを判定せよ。

入力

入力は以下の形式で与えられる。

m
rx1 ry1
:
rxm rym
n
px1 py1 s1 t1
:
pxn pyn sn tn

1 行目には、ビッグブリッジ伯爵が音楽ゲームで使うことのできる指の数を表す整数 m が与えられる。 続く m 行には、それぞれの指がゲームの開始時に置かれている位置を表す 2 つの整数 rx₁, ry₁ が空白区切りで与えられる。 m+2 行目には、音楽ゲームでタッチすべき場所の個数を表す整数 n が与えられる。 続く n 行には、それぞれのタッチすべき位置を表す 2 つの整数 px_i, py_i と、その位置をタッチすべきタイミングを表す 2 つの整数 s_i, t_i が空白区切りで与えられる。

制約

• 1 ≤ m ≤ 3
• 1 ≤ n ≤ 1,000
• 0 ≤ rx_i, ry_i ≤ 1,000
• 0 ≤ px_i, py_i ≤ 1,000
• 0 ≤ s_i < t_i ≤ 1,000
• 1 ≤ i ≤ n - 1 である各 i に対して、t_i = s_i+1

出力

ビッグブリッジ伯爵が音楽ゲームをクリアすることができる場合は YES を、そうでない場合は NO を 1 行に出力せよ。

入出力例

入力例 1

1
0 0
1
1 2 3 4

出力例 1

YES

入力例 2

2
0 0
0 10
3
1 2 3 4
2 3 4 7
5 2 7 8

出力例 2

NO

入力例 3

3
0 0
0 10
10 0
5
1 1 2 3
1 9 3 4
9 1 4 5
3 1 5 6
1 11 6 7

出力例 3

YES