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

Задача

Пересекаются ли отрезки

пересечения точки на плоскости карты и навигация классика собеседования

Даны два отрезка AB и CD на плоскости. Есть ли у них хотя бы одна общая точка? Общая точка может быть концом отрезка, отрезки могут лежать на одной прямой и перекрываться, а отрезок может выродиться в точку, если его концы совпадают.

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

Вход

В первой строке число запросов t (1 ≤ t ≤ 20 000). В каждой из следующих t строк восемь целых чисел xA yA xB yB xC yC xD yD, по модулю не больше 10⁹.

Выход

Для каждого запроса — YES, если у отрезков есть общая точка, и NO, если нет.

Примеры

Пример 1

Вход
9
0 0 4 4 0 4 4 0
0 0 2 2 3 3 5 5
0 0 2 2 2 2 5 0
0 0 4 0 1 1 3 1
0 0 4 0 2 0 6 0
0 0 4 0 2 0 2 5
0 0 4 0 6 0 6 5
3 3 3 3 1 1 5 5
3 3 3 3 3 4 3 4
Выход
YES
NO
YES
NO
YES
YES
NO
YES
NO

Ограничения

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

Разбор

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

1Подсказка 1

Начните с общего случая: когда концы одного отрезка лежат строго по разные стороны от прямой другого? Потом выпишите все случаи, когда какое-то из векторных произведений равно нулю, и нарисуйте каждый.

2Идея

Считаем четыре векторных произведения: d₁ = cross(A, B, C), d₂ = cross(A, B, D), d₃ = cross(C, D, A), d₄ = cross(C, D, B). Если у d₁ и d₂ строго разные знаки и у d₃ и d₄ тоже, отрезки пересекаются во внутренней точке. Во всех остальных случаях, если общие точки есть, среди них найдётся конец одного из отрезков. Значит, достаточно проверить, не лежит ли какой-нибудь из четырёх концов на другом отрезке.

3Разбор

Точка P лежит на отрезке XY, если cross(X, Y, P) = 0 — она на прямой XY — и её координаты не выходят за прямоугольник, натянутый на X и Y: min(xX, xY) ≤ xP ≤ max(xX, xY), и так же по y.

Почему этих пяти проверок хватает? Если пересечение не во внутренней точке обоих отрезков, то либо отрезки лежат на одной прямой, либо одна из четырёх точек лежит на прямой другого отрезка. Если отрезки на одной прямой и перекрываются, то хотя бы один конец одного лежит внутри другого — проверка концов это ловит. Если отрезок выродился в точку A = B, то все произведения с ним равны нулю, строгая проверка не сработает, и ответ даст проверка «A лежит на CD».

Координаты до 10⁹: разности до 2·10⁹, произведение до 4·10¹⁸, векторное произведение до 8·10¹⁸ — помещается в int64. Но произведение d₁·d₂ уже не помещается, поэтому в Go сравнивают знаки, а не перемножают сами числа.

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

O(1) на запрос: восемь умножений на четыре произведения и несколько сравнений.

5Типичные ошибки
  • «≤ 0» вместо проверки концов. Условие d₁·d₂ ≤ 0 и d₃·d₄ ≤ 0 кажется естественным, но для отрезков на одной прямой все произведения равны нулю, и оно отвечает «да» даже при зазоре между ними. Второй пример условия — ровно такой случай.
  • Только строгая проверка. Без проверки концов теряются касания: улицы, которые сходятся на перекрёстке, считаются непересекающимися.
  • Переполнение произведения знаков. В Go d1*d2 при координатах ±10⁹ выходит за int64 и меняет знак.
  • Плавающая точка. Точка пересечения прямых через деление — это дроби и ошибки округления. Для ответа «да или нет» достаточно знаков, а они в целых числах точные.

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

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