Ориентация и пересечение отрезков

Ориентация на службе геометрии: определяем расположение точки и проверяем пересечение отрезков целочисленно.

Два отрезка пересекаются, если концы каждого лежат по разные стороны от прямой, содержащей другой (плюс аккуратная обработка коллинеарных случаев).

Зачем это в олимпиадах

Пересечение отрезков — базовая операция: проверка, пересекаются ли пути, построение планарных структур, заметание плоскости. Делать это через уравнения прямых и деления — путь к ошибкам округления. Правильный олимпиадный подход опирается на ориентацию (косое произведение) и остаётся целочисленным. В этом уроке мы соберём всё из раздела воедино: ориентацию, проверку «точка слева/справа/на отрезке» и устойчивый тест пересечения двух отрезков. Это финал геометрического блока и хороший пример того, как маленькие примитивы складываются в надёжный алгоритм.

С какой стороны точка от прямой

Знак ориентации orient(A, B, C) (косое произведение AB × AC) говорит, с какой стороны от прямой AB лежит точка C: слева (>0), справа (<0) или на прямой (=0). Это и есть основной примитив. Заодно научимся проверять, лежит ли коллинеарная точка на самом отрезке, а не на его продолжении — сравнением координат.

def orient(A, B, C):
    return (B[0] - A[0]) * (C[1] - A[1]) - (B[1] - A[1]) * (C[0] - A[0])

def on_segment(A, B, C):
    # C лежит на отрезке AB при условии, что точки коллинеарны
    return (min(A[0], B[0]) <= C[0] <= max(A[0], B[0]) and
            min(A[1], B[1]) <= C[1] <= max(A[1], B[1]))

A, B = (0, 0), (4, 4)
print(orient(A, B, (1, 2)))      # >0: точка слева от прямой
print(orient(A, B, (2, 1)))      # <0: справа
print(orient(A, B, (2, 2)))      # 0: на прямой
print(on_segment(A, B, (2, 2)))  # True: и на самом отрезке
print(on_segment(A, B, (6, 6)))  # False: на продолжении, вне отрезка

Вывод:

4
-4
0
True
False

Тест пересечения двух отрезков

Отрезки AB и CD пересекаются в общем случае, если точки C и D лежат по разные стороны от прямой AB, и точки A и B — по разные стороны от прямой CD. «По разные стороны» означает, что ориентации имеют противоположные знаки. Формально: orient(A,B,C) и orient(A,B,D) разных знаков, и orient(C,D,A), orient(C,D,B) разных знаков. Отдельно обрабатываем вырожденные (коллинеарные) случаи, когда какая-то ориентация равна нулю и нужно проверить попадание точки на отрезок.

def orient(A, B, C):
    v = (B[0]-A[0])*(C[1]-A[1]) - (B[1]-A[1])*(C[0]-A[0])
    return (v > 0) - (v < 0)          # знак: 1, -1 или 0

def on_segment(A, B, C):
    return (min(A[0],B[0]) <= C[0] <= max(A[0],B[0]) and
            min(A[1],B[1]) <= C[1] <= max(A[1],B[1]))

def segments_intersect(A, B, C, D):
    d1 = orient(A, B, C)
    d2 = orient(A, B, D)
    d3 = orient(C, D, A)
    d4 = orient(C, D, B)
    # общий случай: концы по разные стороны от обеих прямых
    if d1 != d2 and d3 != d4:
        return True
    # вырожденные случаи: коллинеарная точка попадает на отрезок
    if d1 == 0 and on_segment(A, B, C):
        return True
    if d2 == 0 and on_segment(A, B, D):
        return True
    if d3 == 0 and on_segment(C, D, A):
        return True
    if d4 == 0 and on_segment(C, D, B):
        return True
    return False

print(segments_intersect((0,0),(4,4),(0,4),(4,0)))   # крест -> True
print(segments_intersect((0,0),(1,1),(2,2),(3,3)))   # на одной прямой, не касаются -> False
print(segments_intersect((0,0),(2,2),(1,1),(3,3)))   # перекрываются -> True
print(segments_intersect((0,0),(1,0),(2,0),(3,0)))   # параллельны на оси, врозь -> False

Вывод:

True
False
True
False

Тест корректно различает четыре ситуации: пересечение «крестом», непересекающиеся коллинеарные отрезки, перекрывающиеся коллинеарные и параллельные врозь. Вся логика — на знаках ориентации и сравнениях координат, без единого деления и без float. Именно так пишут устойчивую геометрию на олимпиадах.

Почему этот подход надёжен

Алгоритм через уравнения прямых ищет точку пересечения делением — и накапливает ошибку, плюс отдельно мучается с параллельными прямыми (деление на ноль). Подход через ориентацию отвечает на вопрос «пересекаются ли» без нахождения точки пересечения, оставаясь в целых числах. Знак косого произведения точен всегда. Это пример общего принципа вычислительной геометрии: сводите задачу к знакам ориентации, а явные координаты пересечения вычисляйте, только если они действительно нужны.

Разбор олимпиадной задачи: точка внутри многоугольника

Типовая задача: дан простой многоугольник и точка P — лежит ли она внутри? Классический метод трассировки луча (ray casting) использует тот же примитив: пустим из P горизонтальный луч вправо и сосчитаем, сколько рёбер он пересекает. Нечётное число пересечений — точка внутри, чётное — снаружи (луч, выходя из фигуры, пересекает границу нечётное число раз). Реализуется через сравнение ориентаций концов ребра относительно высоты P. Разберём устойчивую версию, обрабатывающую вершины и горизонтальные рёбра аккуратно.

def point_in_polygon(P, poly):
    x, y = P
    n = len(poly)
    inside = False
    j = n - 1
    for i in range(n):
        xi, yi = poly[i]
        xj, yj = poly[j]
        # ребро (j -> i) пересекает горизонтальную прямую уровня y?
        if (yi > y) != (yj > y):
            # x-координата точки пересечения ребра с прямой y
            x_cross = xi + (y - yi) * (xj - xi) / (yj - yi)
            if x < x_cross:
                inside = not inside     # луч вправо пересёк это ребро
        j = i
    return inside

square = [(0, 0), (4, 0), (4, 4), (0, 4)]
print(point_in_polygon((2, 2), square))   # внутри
print(point_in_polygon((5, 2), square))   # снаружи
print(point_in_polygon((2, 5), square))   # снаружи (выше)

# невыпуклый многоугольник: метод работает без изменений
star = [(0, 0), (4, 0), (4, 4), (2, 2), (0, 4)]
print(point_in_polygon((2, 1), star))     # внутри нижней части
print(point_in_polygon((2, 3), star))     # в вырезе — снаружи

Вывод:

True
False
False
True
False

Метод трассировки луча работает и для невыпуклых фигур: точка (2,3) попадает в «вырез» звезды и корректно признана внешней. Условие (yi > y) != (yj > y) отбирает рёбра, чей вертикальный диапазон накрывает уровень P — это аккуратно обходит проблему вершин ровно на луче. Для строго целочисленной версии деление заменяют сравнением косых произведений, но идея — та же: считаем чётность пересечений.

Когда нужна точка пересечения

Иногда мало знать факт пересечения — нужны координаты. Их находят через параметрическое представление: точка на отрезке AB — это A + t·(B−A), t ∈ [0,1]. Приравняв два параметрических уравнения и решив систему, получают t через отношение косых произведений: t = ((C−A)×(D−C)) / ((B−A)×(D−C)). Знаменатель — косое произведение направляющих; если он ноль, отрезки параллельны. Здесь деление неизбежно, поэтому работаем уже в дробях или с плавающей точкой — но только после того, как факт пересечения подтверждён целочисленным тестом.

Разбор подводных камней пересечения

• Коллинеарные случаи. Когда отрезки лежат на одной прямой, общий тест знаков недостаточен — нужна проверка on_segment. Самая частая ошибка — забыть этот случай.
• Касание концом. Если отрезки касаются в одной точке (конец одного на другом), on_segment с нестрогими неравенствами засчитает это как пересечение. Уточняйте по условию задачи: считается ли касание пересечением.
• Знак vs значение. Сравнивайте знаки ориентаций (d1 != d2), а не сами величины — иначе сломаетесь на разных по модулю значениях.
• Переполнение в C++. Косое произведение больших координат требует long long; в Python целые длинные — безопасно.

Итог

• Знак orient(A,B,C) говорит, с какой стороны от прямой AB точка C.
• on_segment проверяет попадание коллинеарной точки на отрезок сравнением координат.
• Отрезки пересекаются, если концы каждого по разные стороны от другого (разные знаки ориентаций), плюс коллинеарные случаи.
• Подход целочислен и устойчив: сводите геометрию к знакам ориентации, избегая float и делений.