← 返回题目列表

AtCoder · utpc2014_d

D. Labo Live Tough 全球音乐节

中文机器翻译题面 查看原题

問題

背景

喜欢音乐游戏的厄尔·比布里奇想要通关某个音乐游戏。 幸运的是,他知道何时何地接触游戏,但比布里奇伯爵不知道他的技能是否真的能让他通关。 因此,您决定查明比格布里奇伯爵能否完成音乐游戏。

課題

Count Bigbridge 在音乐游戏中可以使用的手指数量 m 和每个手指的初始位置 ( 给出rx_i, ry_i)。 另外,在音乐游戏中,触摸的位置和时间应该是 给出了 n 。 为了通关这个音乐游戏,每个 对于 i (1 ≤ i ≤ n) ,在二维平面上 (px_i, py_i) 的位置是什么? 1 多于一根手指的时间 您需要持续触摸它 s_i 到 t_i 。 另外,在该音乐游戏中,触摸各位置的时机是连续的。 也就是说,每个 i (1 ≤ i ≤ n - 1) , 定义t_i = s_{i+1} 。 Bigbridge 伯爵独立使用每个手指,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 行包含一个整数,表示 Count Bigbridge 在音乐游戏中可以使用的手指数量。 给出了 m 。 继续 m 线代表游戏开始时每个手指的位置。 2 整数 rx_1, ry_1 用空格分隔。 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}

出力

如果Bigbridge伯爵可以通关音乐游戏 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