Площадь треугольника и многоугольника

Площадь треугольника и многоугольника через косое произведение — формула шнурков, работающая в целых числах.

Формула площади (шнурков, Гаусса): площадь многоугольника выражается через сумму косых произведений координат его последовательных вершин.

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

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

Площадь треугольника

Удвоенная ориентированная площадь треугольника ABC равна косому произведению векторов AB и AC: 2S = (B−A) × (C−A). Знак отражает ориентацию обхода (против часовой — плюс), а модуль, делённый на 2, — площадь. Поскольку косое произведение целочисленно при целых координатах, 2S — целое, и площадь либо целая, либо полуцелая. Это объясняет, почему площади многоугольников с целыми вершинами всегда кратны 1/2.

def cross(O, A, B):
    # косое произведение векторов OA и OB
    return (A[0] - O[0]) * (B[1] - O[1]) - (A[1] - O[1]) * (B[0] - O[0])

def triangle_area2(A, B, C):
    return abs(cross(A, B, C))     # удвоенная площадь (целое)

A, B, C = (0, 0), (4, 0), (0, 3)
print(triangle_area2(A, B, C))     # 12 = 2 * 6
print(triangle_area2(A, B, C) / 2) # 6.0 — площадь
# вырожденный треугольник (точки на прямой) -> площадь 0
print(triangle_area2((0, 0), (1, 1), (2, 2)))

Вывод:

12
6.0
0

Формула шнурков для многоугольника

Формула шнурков: для многоугольника с вершинами (x₀,y₀), …, (xₙ₋₁,yₙ₋₁) в порядке обхода удвоенная площадь равна |∑ᵢ (xᵢ·yᵢ₊₁ − xᵢ₊₁·yᵢ)|, где индексы циклические.

Название «шнурков» — от того, как координаты перемножаются крест-накрест, словно шнуровка ботинка. Интуиция: каждое слагаемое xᵢyᵢ₊₁ − xᵢ₊₁yᵢ — это удвоенная ориентированная площадь треугольника, образованного началом координат и ребром (i, i+1). Суммируя по всем рёбрам, «лишние» части за пределами многоугольника взаимно сокращаются благодаря знакам, и остаётся ровно площадь.

def polygon_area2(points):
    n = len(points)
    s = 0
    for i in range(n):
        x1, y1 = points[i]
        x2, y2 = points[(i + 1) % n]   # следующая вершина (циклически)
        s += x1 * y2 - x2 * y1
    return abs(s)                       # удвоенная площадь

# квадрат 4x3
square = [(0, 0), (4, 0), (4, 3), (0, 3)]
print(polygon_area2(square), polygon_area2(square) / 2)   # 24, 12.0

# невыпуклый L-образный многоугольник
poly = [(0, 0), (4, 0), (4, 2), (2, 2), (2, 4), (0, 4)]
print(polygon_area2(poly) / 2)         # площадь L-фигуры

Вывод:

24 12.0
12.0

Формула шнурков работает для любого простого многоугольника — выпуклого или нет, как видно на L-образной фигуре (её площадь 12). Важно лишь, чтобы вершины шли по порядку обхода границы. Берём модуль, чтобы не зависеть от направления обхода (по или против часовой стрелки).

Применение: теорема Пика (связь с целыми точками)

Красивый мост от площади к подсчёту: теорема Пика утверждает, что площадь многоугольника с вершинами в целых точках равна S = I + B/2 − 1, где I — число целых точек строго внутри, B — на границе. Зная площадь (по шнуркам) и число граничных точек (через НОД координат рёбер), можно найти число внутренних точек. Это типовой приём счётных геометрических задач.

import math

def polygon_area2(points):
    n = len(points)
    return abs(sum(points[i][0] * points[(i+1) % n][1]
                   - points[(i+1) % n][0] * points[i][1] for i in range(n)))

def boundary_points(points):
    n = len(points)
    b = 0
    for i in range(n):
        x1, y1 = points[i]
        x2, y2 = points[(i + 1) % n]
        b += math.gcd(abs(x2 - x1), abs(y2 - y1))   # целые точки на ребре
    return b

square = [(0, 0), (4, 0), (4, 4), (0, 4)]
area2 = polygon_area2(square)        # удвоенная площадь = 32
B = boundary_points(square)          # точки на границе
# Пик: S = I + B/2 - 1  =>  I = S - B/2 + 1 = area2/2 - B/2 + 1
I = area2 // 2 - B // 2 + 1
print(area2 // 2, B, I)              # площадь, граница, внутренние

Вывод:

16 16 9

Квадрат 4×4: площадь 16, на границе 16 целых точек, внутри 4×4 = 9? Проверим: внутренние точки — это (1..3)×(1..3) = 9. Совпало! Теорема Пика связала непрерывную площадь с дискретным подсчётом точек — частый трюк, превращающий геометрию в комбинаторику.

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

Есть и другой взгляд на формулу шнурков, который часто проще объяснить и обобщить. Зафиксируем любую точку O (удобно — начало координат) и разобьём многоугольник на треугольники O, Vᵢ, Vᵢ₊₁ по всем рёбрам. Ориентированная площадь многоугольника — это сумма ориентированных площадей этих треугольников: те, что «снаружи», входят со знаком минус и сокращают лишнее. Это объясняет, почему берётся именно косое произведение и почему важна ориентация обхода.

def signed_area2(points):
    O = (0, 0)
    total = 0
    n = len(points)
    for i in range(n):
        A = points[i]
        B = points[(i + 1) % n]
        # удвоенная ориентированная площадь треугольника O, A, B
        total += A[0] * B[1] - A[1] * B[0]
    return total       # знак зависит от направления обхода

# Тот же квадрат, обойдённый против и по часовой стрелке
ccw = [(0, 0), (4, 0), (4, 3), (0, 3)]   # против часовой
cw = [(0, 0), (0, 3), (4, 3), (4, 0)]    # по часовой
print(signed_area2(ccw))    # +24: положительная ориентация
print(signed_area2(cw))     # -24: отрицательная
print(abs(signed_area2(ccw)) // 2)   # площадь = 12

Вывод:

24
-24
12

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

Подводные камни

• Порядок вершин. Формула шнурков требует вершины в порядке обхода границы; перемешанные дадут бессмыслицу.
• Циклический индекс. Не забудьте замкнуть многоугольник: последнее ребро соединяет последнюю вершину с первой ((i+1) % n).
• Удвоенная площадь. Формула даёт 2S; делите на 2 в конце. Держать 2S целым — способ избежать float.
• Самопересечения. Шнурки верны для простых (без самопересечений) многоугольников.

Итог

• Удвоенная площадь треугольника = модуль косого произведения (B−A)×(C−A).
• Формула шнурков: 2S = |∑(xᵢyᵢ₊₁ − xᵢ₊₁yᵢ)| для любого простого многоугольника.
• Вершины — в порядке обхода; индекс циклический; держите 2S целым.
• Теорема Пика S = I + B/2 − 1 связывает площадь и целые точки.