D. Шестерни
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

На плоскости расположены два многоугольника A и B. Многоугольник A вращается вокруг точки P, а многоугольник B — вокруг точки Q. Каждый многоугольник вращается с постоянной угловой скоростью по часовой стрелке вокруг своей точки, угловые скорости вращения многоугольников совпадают.

Требуется определить, произойдет ли когда-нибудь столкновение между многоугольниками. Под столкновением подразумевается ситуация, в которой многоугольники имеют хотя бы одну общую точку.

Гарантируется, что в момент времени 0 многоугольники A и B не пересекаются, и ни один из многоугольников не содержится целиком внутри другого.

Обратите внимание, что:

  • многоугольники могут не являться выпуклыми;
  • точки P и Q могут находиться на границе или вне своих многоугольников.
Входные данные

В первой строке через пробел записаны координаты точки P.

Во второй строке записано одно целое число n (3 ≤ n ≤ 1000) — количество вершин многоугольника A.

В каждой их следующих n строк записано по два числа, разделенных пробелом — координаты очередной вершины многоугольника A.

Следующая строка оставлена пустой.

Далее следуют через пробел координаты точки Q.

В следующей строке находится одно целое число m (3 ≤ m ≤ 1000) — количество вершин многоугольника B. Далее в m строках в аналогичном формате описаны координаты координаты вершин многоугольника B.

Вершины обоих многоугольников перечислены в порядке обхода против часовой стрелки. Все координаты точек — целые числа, по модулю не превосходящие 104.

Выходные данные

Выведите «YES», если столкновение произойдет, и «NO» в противном случае.

Примеры
Входные данные
1 0
4
0 0
1 0
1 5
0 5

9 0
4
9 0
9 -5
10 -5
10 0
Выходные данные
YES
Входные данные
0 0
3
1 0
2 -1
2 1

0 0
3
-1 0
-2 1
-2 -1
Выходные данные
NO
Примечание

Многоугольником называется замкнутая ломаная без самопересечений и самокасаний.

Картинка к первому примеру: