Перекрёсток: внутри, снаружи или на границе
Городская служба раздаёт районам перекрёстки: каждый перекрёсток обслуживает тот район, внутри которого он стоит. Но границы районов часто проведены прямо по улицам, и перекрёсток может оказаться точно на границе — такие служба делит отдельно, и их нужно найти без ошибок. Дан район — многоугольник, и список перекрёстков. Для каждого скажите, внутри района он, снаружи или на границе.
Второй и третий тесты — Алмалинский и Бостандыкский районы Алматы и перекрёстки вокруг них из OpenStreetMap, в целых метрах на сетке карты дорог этого каталога.
Вход
В первой строке число вершин n (3 ≤ n ≤ 2000), дальше n строк с координатами вершин x y в порядке обхода, по часовой стрелке или против. Многоугольник простой: стороны не пересекаются и не касаются, кроме соседних в общей вершине; вершины не повторяются, три вершины подряд могут лежать на одной прямой. Затем число перекрёстков q (1 ≤ q ≤ 1000) и q строк с их координатами. Все координаты целые, |x|, |y| ≤ 10⁹.
Выход
Для каждого перекрёстка в отдельной строке: inside, если он строго внутри многоугольника, outside, если строго снаружи, и border, если на стороне или в вершине.
Примеры
Пример 1
11 0 0 12 0 13 3 12 6 10 3 8 6 6 3 4 6 2 3 0 6 -1 3 10 1 3 5 3 11 3 3 1 9 5 6 3 14 3 -1 3 -2 3 12 6
inside inside inside inside outside border outside border outside border
Ограничения
- Время · Python
- 6000 мс
- Время · Go
- 1500 мс
- Память
- 256 МБ
- Проверка
- 10 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Проведите из перекрёстка луч на восток и посчитайте, сколько раз он пересекает границу. Нечётное число — внутри. Теперь нарисуйте луч, который проходит точно через вершину многоугольника. Сколько пересечений вы насчитаете, если граница идёт через луч насквозь? А если только касается его снизу?
2Подсказка 2
Правило, которое решает все случаи с вершинами сразу: сторона считается пересечённой, если ровно один её конец лежит строго выше луча. Горизонтальные стороны при этом не считаются никогда. Проверьте это правило на вершине, через которую граница проходит насквозь, и на вершине-впадине.
3Идея
Сначала граница: точка лежит на стороне AB, если векторное произведение cross(A, B, P) равно нулю и точка внутри прямоугольника, натянутого на A и B. Если ни на одной стороне её нет, считаем пересечения луча на восток по полуоткрытому правилу. Всё в целых числах: ни деления, ни дробей.
4Разбор
Для каждой стороны A → B и точки P считаем s = cross(A, B, P). Если s = 0 и P в прямоугольнике концов — ответ border. Иначе, если ровно одно из Ay > Py, By > Py верно, сторона пересекает прямую луча. Пересечение восточнее точки, когда точка слева от стороны, идущей вверх (s > 0), или справа от идущей вниз (s < 0): это одно условие (s > 0) = (By > Ay). Каждое такое пересечение переключает «внутри/снаружи».
Почему правило верно у вершин. Оно считает вершину на луче лежащей чуть ниже него. Если граница проходит через луч насквозь, одна из двух сторон при вершине уходит вверх, другая — вниз, и посчитана ровно одна: одно пересечение, как и должно быть. Если граница касается луча снизу или сверху, обе стороны по одну сторону — посчитаны обе или ни одной, чётность не меняется. Горизонтальная сторона на луче не имеет концов строго выше и строго ниже одновременно и не считается — её соседи решат всё сами.
Переполнения нет: разности координат до 2·10⁹, произведения до 4·10¹⁸, их разность до 8·10¹⁸ — это помещается в int64.
4+Решение
5Сложность
O(n) на перекрёсток, O(nq) всего: до двух миллионов проверок сторон. Если бы перекрёстков были миллионы, стоило бы разложить стороны по горизонтальным полосам, как в статье: тогда каждый луч смотрит только на стороны своей полосы.
6Типичные ошибки
- Концы сторон включены. Сторона считается, если y точки в отрезке [min, max] её концов. Луч через вершину, где граница идёт насквозь, задевает обе стороны при ней, и пересечение считается дважды. Это неверное решение задачи. На Алмалинском районе из второго теста оно ошибается на 46 перекрёстках из тысячи: границы районов проведены через перекрёстки, и лучи то и дело попадают в вершины.
- Пересечение через деление. Вычислить x пересечения как дробь и сравнить с x точки в
double— при координатах около 10⁹ погрешность решает, по какую сторону точка, а точки на самой стороне становятся то внутренними, то внешними. - Граница по пересечениям. Пытаться заметить «на границе» по ходу подсчёта пересечений, а не отдельной проверкой: точки на горизонтальных сторонах и в вершинах-впадинах так не ловятся.
Алгоритмы задачи
O(n) на точку
2 задачи
GEO
Приём
Векторы и ориентация
Знак векторного произведения — поворот налево или направо; на нём стоит почти вся вычислительная геометрия.
O(1) на один поворот
2 задачи