Граница без петель
Картографическая программа упростила границу участка — замкнутую ломаную — и теперь должна проверить, что граница осталась границей: нигде не пересекает и не касается сама себя. Соседние стороны встречаются только в общей вершине, несоседние вообще не имеют общих точек. Вершина на прямом участке стороны — когда две соседние стороны лежат на одной прямой и продолжают друг друга — допустима, а сторона, которая возвращается назад по предыдущей, — нет.
Вход
В первой строке — n (3 ≤ n ≤ 105), число вершин. Дальше n строк: координаты вершин x y по порядку обхода, целые, 0 ≤ x, y ≤ 106. Последняя вершина соединена с первой. Соседние вершины, включая последнюю и первую, различны.
Выход
YES, если граница не пересекает и не касается сама себя, иначе NO.
Примеры
Пример 1
4 0 0 4 0 4 3 0 3
YES
Пример 2
4 0 0 4 3 4 0 0 3
NO
Ограничения
- Время · Python
- 11500 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 12 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Проверять все пары сторон — 5 · 109 пар. Но если две стороны пересекаются, то где-то левее точки пересечения вертикальная прямая встречает их рядом, без сторон между ними.
2Подсказка 2
Достаточно найти хотя бы одно пересечение, а не все. Значит, точки пересечения не нужно делать событиями: события — только вершины, и до первого найденного пересечения порядок сторон на прямой не меняется.
3Идея
Алгоритм Шеймоса — Хоуи, частный случай заметающей прямой. Вершины обходим слева направо (при равных x — снизу вверх). Состояние — стороны, которые пересекает вертикаль, в порядке снизу вверх. В вершине стороны, которые в ней кончаются, уходят из состояния, начинающиеся — встают на их место, и проверяются только новые пары соседей. Если ни одна проверка не нашла общей точки, пересечений нет.
4Разбор
Сначала два особых случая: вершина, которая встречается дважды, и сторона, которая идёт назад по предыдущей (векторное произведение соседних сторон равно нулю, скалярное больше нуля). Дальше сторона хранится концами слева направо. В вершине q двоичный поиск находит в состоянии стороны, проходящие через q: положение стороны относительно q — знак векторного произведения. Если среди них есть сторона, которой q не принадлежит как вершина, вершина лежит на чужой стороне — ответ NO. Иначе это две стороны самой вершины; их заменяем начинающимися сторонами, упорядоченными по наклону (вертикальная — выше всех), и проверяем соседей снизу и сверху. Все вычисления целые: произведения не больше 1012.
4+Решение
5Сложность
O(n log n) сравнений: сортировка вершин и по двоичному поиску на вершину. Вставка в массив сдвигает хвост, но это один memmove; на гребёнке из теста 7, где вертикаль пересекает половину сторон сразу, сдвиги не становятся узким местом.
6Типичные ошибки
- Все пары. Это
wrong.py: на звезде из ста тысяч вершин он не успевает. - Проверка только при вставке. Когда сторона уходит, её соседи снизу и сверху становятся соседями друг друга — их тоже надо проверить.
- Касание вершиной. Вершина, лежащая на чужой стороне, — тоже пересечение (тест 8: кончик зубца ровно на стороне соседнего). Его ловит проверка «через q проходит чужая сторона».
- Вертикальные стороны. У них нет высоты «на вертикали»; если сравнивать вершины сначала по x, а потом по y, вертикальная сторона идёт снизу вверх и в своей нижней вершине встаёт выше всех остальных сторон оттуда.
- Числа с плавающей точкой. Касание — это равенство нулю векторного произведения; в целых числах оно точное.
Алгоритмы задачи
O((n + k) log n)
3 задачи
GEO
Алгоритм
Пересечение отрезков
Где встречаются два отрезка — точно, в дробях; и как найти все встречи среди тысяч отрезков без перебора пар.
O(1) на пару; O(n²) перебором для n отрезков
2 задачи