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

Задача

Где встречаются отрезки

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

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

Вход

В первой строке число пар q (1 ≤ q ≤ 10 000). Каждая следующая строка — восемь целых чисел x1 y1 x2 y2 x3 y3 x4 y4: первый отрезок от (x1, y1) до (x2, y2), второй — от (x3, y3) до (x4, y4). Все координаты по модулю не больше 10⁹. Концы отрезка могут совпадать — тогда это точка.

Выход

Для каждой пары одну строку:

  • NONE, если общих точек нет;
  • POINT x y, если общая точка одна: каждая координата — несократимая дробь p/q с q > 1 или целое число, минус — перед числителем;
  • SEGMENT x1 y1 x2 y2, если общих точек бесконечно много: концы общего отрезка, сначала тот, у которого меньше x, а при равных x — меньше y.

Примеры

Пример 1

Вход
8
0 0 4 3 0 3 5 0
0 0 6 0 2 0 2 5
0 0 2 2 2 2 5 0
0 0 4 2 2 1 8 4
0 0 2 1 4 2 8 4
0 0 4 2 0 1 4 3
0 0 10 1 10 2 11 0
-999999937 3 999999929 999999893 5 -999999883 -17 999999991
Выход
POINT 20/9 5/3
POINT 2 0
POINT 2 2
SEGMENT 2 1 4 2
NONE
NONE
NONE
POINT -2874999426875025257/249999968875000904 124999970500002335124935227/249999968875000904

Ограничения

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

Разбор

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

1Подсказка 1

Запишите отрезки как A + t·(B − A) и C + u·(D − C), 0 ≤ t, u ≤ 1, и приравняйте. Как найти t, не решая систему в лоб? Подсказка: векторное произведение вектора на самого себя равно нулю.

2Подсказка 2

Если векторное произведение направлений отрезков равно нулю, формулы для t и u не работают. Не спешите отвечать NONE: что, если все четыре точки на одной прямой?

3Идея

Пусть r = B − A, s = D − C, den = r × s. Если den ≠ 0, то t = (C − A) × s / den и u = (C − A) × r / den; отрезки встречаются, если оба числа в [0, 1], — проверка в целых, без деления. Точка A + t·r — дробь. Если den = 0 и точки не на одной прямой — ответ NONE; если на одной — сравниваем отрезки вдоль прямой, как отрезки на числовой оси.

4Разбор

Непараллельные. Числители tn = (C − A) × s и un = (C − A) × r; если den < 0, меняем знаки у всех трёх. Встречаются, если 0 ≤ tn ≤ den и 0 ≤ un ≤ den. Координаты точки: x = (Ax·den + tn·rx) / den, и так же y; дробь сокращаем на наибольший общий делитель — Fraction в Python и big.Rat в Go делают это сами.

Параллельные. Если C или D не лежит на прямой AB (или, когда A = B, точка A не на прямой CD), общих точек нет. Иначе все точки на одной прямой, и вдоль неё они упорядочены так же, как пары (x, y) в лексикографическом порядке: по x, а на вертикальной прямой — по y. Упорядочим концы каждого отрезка, возьмём lo = max из левых концов и hi = min из правых. lo > hi — зазор, lo = hi — одна точка, иначе общий отрезок от lo до hi. Отрезки-точки этот разбор обрабатывает без отдельных случаев.

Размер чисел. Разности координат до 2·10⁹, векторные произведения до 8·10¹⁸ — на грани int64. Числитель координаты точки — до 10²⁸, это уже 94 бита. В Python об этом думать не нужно, в Go нужен math/big: восьмой пример из условия — пара отрезков, у которой числитель y — 27-значное число.

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

O(1) арифметических действий на пару, но с длинными числами: каждое — над числами в два-три машинных слова.

6Типичные ошибки
  • Параллельные — значит, не встречаются. Самая частая ошибка: при нулевом знаменателе ответить NONE. Отрезки на одной прямой могут налегать друг на друга или касаться концами. Это неверное решение задачи — его ловит уже пример.
  • Точка в числах с плавающей точкой. Даже если потом подобрать дробь, близкую к double, при координатах около 10⁹ она будет не той: double помнит около 16 значащих цифр, а у ответа их бывает за двадцать.
  • Переполнение. Числитель координаты не помещается в int64, и решение на Go без math/big печатает мусор именно на больших тестах, хотя на маленьких всё верно.
  • Несокращённые дроби и -0. Ответ сравнивается как строка: дробь должна быть несократимой, знаменатель положительным, ноль — просто 0.

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

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