東京大学プログラミングコンテスト2014

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


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

問題

背景

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

課題

ビッグブリッジ伯爵が音楽ゲームで使うことのできる指の数 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 の速度で任意の方向に動かすことができる。 ビッグブリッジ伯爵がこの音楽ゲームをクリアすることができるかどうかを判定せよ。

配点

200

入力

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

m
rx_1 ry_1
:
rx_m ry_m
n
px_1 py_1 s_1 t_1
:
px_n py_n s_n t_n

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

制約

出力

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

入出力例

入力例 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

Submit提出する