Задача №113787. Открытый кубок
К 3017 году человечество наконец освоило межпланетные перелёты на таком уровне, что одним из самых популярных видов спорта стали гонки между астероидами. Через два дня состоится один из этапов Открытого кубка по межастероидным гонкам, который проводит известный популяризатор гонок Спарк.
Спарк любит считать статистику по заездам лучших участников и с удовольствием рассказывает интересные истории про разные этапы чемпионата и участников. В одном из рассказов он проговорился, что этап через два дня будет называться «Гран-При Альфа Центавры». Альфа Центавра — система хорошо изученная, и любому, кто понимает правила гонок, понятно, что участникам будет предложено долететь от астероида ICM-2017 до астероида YOY-2018.
Гонки всегда проходят в одной плоскости. Будем считать, что во время гонки астероиды не изменяют своё взаимное расположение. В плоскости, в которой проходит гонка, оба астероида можно представить как два непересекающихся и не касающихся выпуклых многоугольника, заданных координатами их вершин в порядке обхода против часовой стрелки.
Гоночный болид может стартовать и приземляться лишь перпендикулярно поверхности астероида. Для старта болида нужно выбрать точку строго внутри одной из сторон многоугольника. Стартовав из этой точки, болид летит в направлении, перпендикулярном этой стороне, удаляясь от астероида. Подлетев к другому астероиду, болид должен осуществить посадку в точку строго внутри одной из сторон многоугольника, перпендикулярно этой стороне.
Начинающий гонщик Эльбрус планирует принять участие в гонке, но он мало практиковался и не умеет маневрировать в космосе. К счастью, может оказаться, что между астероидами есть прямой маршрут и болид может долететь от одного астероида до другого, ни в какой момент времени не поворачивая. Иначе говоря, можно выбрать точки старта и финиша так, что отрезок между ними перпендикулярен сторонам, на которых лежат точки, и не проходит через внутреннюю часть астероидов. Помогите Эльбрусу выяснить, сможет ли он принять участие в гонке.
В первой строке дано целое число n — количество вершин в многоугольнике, задающем астероид ICM-2017 (3 ≤ n ≤ 200 000). В следующих n строках даны пары чисел xi, yi — координаты вершин многоугольника ICM-2017 ( - 109 ≤ xi, yi ≤ 109).
В следующей строке дано целое число m — количество вершин в многоугольнике, задающем астероид YOY-2018 (3 ≤ m ≤ 200 000). В следующих m строках даны пары чисел x'i, y'i — координаты вершин многоугольника YOY-2018 ( - 109 ≤ x'i, y'i ≤ 109).
Гарантируется, что оба многоугольника выпуклые, их вершины даны в порядке обхода против часовой стрелки, никакие три вершины одного многоугольника не лежат на одной прямой.
Если можно найти прямой маршрут между многоугольниками, выведите в первой строке «YES», а во второй строке номера сторон астероидов ICM-2017 и YOY-2018, между которыми есть прямой маршрут.
Считайте, что сторона i соединяет вершины i и i + 1 многоугольника, сторона n многоугольника ICM-2017 соединяет вершины n и 1, а сторона m многоугольника YOY-2018 — вершины m и 1.
Если такого маршрута между многоугольниками нет, выведите единственное слово «NO».
3
0 0
1 0
0 1
3
0 -1
0 -2
1 -1
YES
1 3
3
0 0
1 0
0 1
3
1 -1
1 -2
2 -1
NO
4
-1 0
0 0
0 1
-1 1
4
1 0
0 -1
1 -2
2 -1
NO
3 0 0 1 0 0 1 3 0 -1 0 -2 1 -1
YES 1 3
3 0 0 1 0 0 1 3 1 -1 1 -2 2 -1
NO
4 -1 0 0 0 0 1 -1 1 4 1 0 0 -1 1 -2 2 -1
NO