eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Игра с геометрией

Игра с геометрией

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB
prb7918.gif

Программное обеспечение динамической геометрии может помочь студентам понять геометрию преобразования, поскольку оно позволяет визуализировать эффект преобразований на фигуре. Алиса изучает элементарные преобразования - скольжение, переворачивание и повороты - или, более формально, параллельный перенос, отражения и вращения. Сегодня она исследует скольжение и повороты. Она работает с простыми прямолинейными многоугольниками, нарисованными на правильной квадратной сетке. Длина каждого ребра многоугольника пропорциональна длине линии сетки, а вершины многоугольника являются точками сетки.

Алиса знает, что: прямолинейный многоугольник - это многоугольник, стороны которого пересекаются под прямым углом; в простом многоугольнике ребра пересекаются только на концах; вершины - это точки пересечения ребер; область, ограниченная прямолинейным многоугольником, встроенным в сетку, соответствует полимино (образованному единичными квадратами); пермутомино - это полимино, у которого есть ровно одно ребро на всех линиях сетки, пересекающих его минимальный ограничивающий прямоугольник; этот прямоугольник на самом деле является квадратом (для n - вершинного пермутомино, он пересекает n / 2 горизонтальных и вертикальных линий сетки). Ее учитель объяснил, как скольжения и повороты действуют на координаты точек, но к тому времени Алиса уже думала об эпизоде "Симпсонов", в котором Гомер утверждал, что в его мозгу больше нет места для дополнительной информации.

Теперь она должна решить, могут ли два простых прямолинейных многоугольника без коллинеарных ребер быть преобразованы в одно и то же пермутомино с помощью скольжения и поворотов при некоторых ограниченных правилах. Два полигона обрабатываются как независимые экземпляры, как если бы они находились в разных сетках. Во-первых, она должна удалить пустые линии сетки из минимального ограничивающего прямоугольника, чтобы получить пермутомино. Это делается путем сдвига некоторых ребер влево или вниз таким образом, чтобы сохранялся относительный порядок ребер (то есть они будут происходить в том же порядке, что и раньше, если мы проведем плоскость, используя вертикальную или горизонтальную линию). Как только она получит пермутомино, то может применить поворот на 90 градусов по часовой стрелке вокруг центра его минимального ограничивающего квадрата сколько раз она пожелает.

Сможем ли мы дать ответ на проблему Алисы для пары таких многоугольников?

Вхідні дані

Первая строка содержит описание первого прямолинейного многоугольника: количество вершин, за которыми следуют их координаты в канонической декартовой системе. Последовательность вершин дана в порядке против часовой стрелки и начинается с самой левой вершины на нижнем горизонтальном ребре. Последнее вертикальное ребро определяется последней и первой вершиной в последовательности. Левый нижний угол минимального ограничивающего прямоугольника всегда (0, 0). Следующая строка содержит аналогичное описание для другого прямолинейного многоугольника. Количество вершин двух полигонов может быть разным (на рисунке показан пример 1).

Для каждого многоугольника: количество вершин четное от 4 до 500; координаты (x, y) каждой вершины удовлетворяют 0x3000 and 0y3000.

Вихідні дані

Выведите строку с ответом yes или no.

Приклад

Вхідні дані #1
16 3 0 8 0 8 1 12 1 12 3 10 3 10 5 9 5 9 12 6 12 6 8 5 8 5 10 0 10 0 6 3 6
16 1 0 2 0 2 1 3 1 3 2 12 2 12 4 7 4 7 6 9 6 9 9 6 9 6 8 0 8 0 3 1 3
Вихідні дані #1
yes
Вхідні дані #2
10 3 0 4 0 4 2 1 2 1 3 2 3 2 4 0 4 0 1 3 1
10 0 0 4 0 4 3 5 3 5 6 3 6 3 2 1 2 1 4 0 4
Вихідні дані #2
no
Джерело 2014 ACM Southwestern Europe Regional Contest (SWERC), Задача G