CS
Задачник Базовый курс EN

Задача

Сколько кругов

многоугольник точки на плоскости карты и навигация олимпиады

Бегун записал тренировку: три круга по городу, каждый от площади Республики по кратчайшим улицам через несколько достопримечательностей и обратно. Трек — замкнутая ломаная, которая пересекает себя, местами идёт по одной улице дважды и в обе стороны. Тренер хочет знать про каждую точку на карте, сколько раз бегун её обежал. Обход против часовой стрелки считается за +1, по часовой — за −1, так что круг туда и круг обратно в сумме дают ноль.

Второй тест — такая тренировка по улицам Алматы из OpenStreetMap, в целых метрах на сетке карты дорог этого каталога; точки — достопримечательности и перекрёстки, мимо которых трек не проходит.

Вход

В первой строке число вершин трека n (3 ≤ n ≤ 2000), дальше n строк с координатами x y в порядке движения; после последней вершины бегун возвращается в первую. Соседние вершины различны, но в остальном трек может что угодно: пересекать себя, проходить через одни и те же точки, идти по уже пройденным отрезкам. Затем число точек q (1 ≤ q ≤ 1000) и q строк с их координатами. Ни одна точка не лежит на треке. Все координаты целые, |x|, |y| ≤ 10⁹.

Выход

Для каждой точки в отдельной строке — целое число: сколько раз трек обходит её против часовой стрелки за вычетом обходов по часовой.

Примеры

Пример 1

Вход
12
-4 -4
4 -4
4 4
-4 4
-3 -3
3 -3
3 1
8 1
8 -2
3 -2
3 3
-3 3
6
0 0
6 0
-6 0
-3 0
6 3
0 -5
Выход
2
-1
0
2
0
0

Ограничения

Время · Python
6000 мс
Время · Go
1500 мс
Память
256 МБ
Проверка
7 тестов

Разбор

Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.

1Подсказка 1

Представьте, что вы стоите в точке и поворачиваетесь лицом к бегуну, пока он бежит по треку. На сколько полных оборотов вы повернётесь к концу тренировки? Это и есть ответ — число оборотов трека вокруг точки.

2Подсказка 2

Складывать углы через atan2 можно, но есть способ без тригонометрии. Проведите из точки луч на восток. Каждый раз, когда трек пересекает луч, идя вверх, вы поворачиваетесь через восток против часовой стрелки; идя вниз — по часовой.

3Идея

Число оборотов равно сумме по пересечениям луча: +1 за отрезок, который пересекает луч снизу вверх, −1 — сверху вниз. Чётность этой суммы — обычный тест «внутри или снаружи» по лучу; сама сумма знает больше: сколько раз и в какую сторону.

4Разбор

Для отрезка A → B и точки P считаем s = cross(A, B, P). Отрезок идёт вверх через луч, если Ay ≤ Py < By; пересечение восточнее точки, если точка слева от отрезка, s > 0. Тогда +1. Отрезок идёт вниз, если By ≤ Py < Ay, и пересечение восточнее, если точка справа, s < 0. Тогда −1.

Почему это число оборотов. Направление от точки на бегуна проходит через восток ровно тогда, когда бегун пересекает луч. Если он пересекает его, двигаясь вверх, направление поворачивается против часовой стрелки, если вниз — по часовой. Каждый полный оборот проходит через восток один раз, поэтому сумма ±1 по пересечениям — это число полных оборотов со знаком. Полуоткрытые неравенства (одна граница с «≤», другая с «<») решают случай, когда луч проходит через вершину трека: из двух отрезков при вершине посчитан будет не больше чем один, и только если трек идёт через луч насквозь. Повторно пройденные отрезки не мешают: туда и обратно по одной улице дают +1 и −1.

Так считают заливку правилом nonzero в SVG и на холсте браузера: точка закрашена, если число оборотов не ноль.

4+Решение
5Сложность

O(n) на точку, O(nq) всего — два миллиона проверок отрезков в худшем случае, всё в целых числах.

6Типичные ошибки
  • Чётность вместо суммы. Тест «луч пересёк границу нечётное число раз» отвечает только 0 или 1 и теряет знак. Это неверное решение задачи: в спирали из третьего теста точки у центра обойдены 450 раз.
  • Пересечения без знака. Считать все пересечения луча и делить на два — неверно: круг по часовой стрелке и круг против дают вместе ноль, а не два.
  • Углы в double. Сумма углов через atan2 верна, если в конце округлить её до целого числа оборотов, но это тригонометрия на каждом отрезке, а у точек вплотную к треку погрешность растёт. Знаки пересечений дают тот же ответ в целых числах.
  • Концы отрезков с обеих сторон включены. Луч через вершину, где трек идёт насквозь, тогда считается дважды.

Алгоритмы задачи

GEO Алгоритм Точка в многоугольнике Луч из точки пересекает границу нечётное число раз — точка внутри; число оборотов — то же со знаками. O(n) на точку 2 задачи GEO Приём Векторы и ориентация Знак векторного произведения — поворот налево или направо; на нём стоит почти вся вычислительная геометрия. O(1) на один поворот 2 задачи
Каталог алгоритмов