Codeforces Round 283 (Div. 1) |
---|
Закончено |
На плоскости расположены два многоугольника A и B. Многоугольник A вращается вокруг точки P, а многоугольник B — вокруг точки Q. Каждый многоугольник вращается с постоянной угловой скоростью по часовой стрелке вокруг своей точки, угловые скорости вращения многоугольников совпадают.
Требуется определить, произойдет ли когда-нибудь столкновение между многоугольниками. Под столкновением подразумевается ситуация, в которой многоугольники имеют хотя бы одну общую точку.
Гарантируется, что в момент времени 0 многоугольники A и B не пересекаются, и ни один из многоугольников не содержится целиком внутри другого.
Обратите внимание, что:
В первой строке через пробел записаны координаты точки 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
Многоугольником называется замкнутая ломаная без самопересечений и самокасаний.
Картинка к первому примеру:
Название |
---|