Базовая геометрия

Что такое точка?

Точка на плоскости задается двумя координатами:

(x, y)

Например:

A = (2, 3)
B = (5, 7)

В C++ удобно хранить точку как структуру:

struct Point {
    long long x;
    long long y;
};

Что такое вектор?

Вектор показывает направление и длину перемещения.

Если есть две точки A и B, то вектор из A в B:

AB = (B.x - A.x, B.y - A.y)

Например:

A = (2, 3)
B = (5, 7)

AB = (5 - 2, 7 - 3) = (3, 4)

Структура Point с операциями

struct Point {
    long long x;
    long long y;

    Point operator + (const Point &other) const {
        return {x + other.x, y + other.y};
    }

    Point operator - (const Point &other) const {
        return {x - other.x, y - other.y};
    }
};

Теперь можно писать:

Point v = b - a;

Это будет вектор из точки a в точку b.

Расстояние между двумя точками

Расстояние между точками A(x1, y1) и B(x2, y2) считается по формуле:

dist = sqrt((x2 - x1)^2 + (y2 - y1)^2)

Например:

A = (0, 0)
B = (3, 4)

dist = sqrt(3^2 + 4^2) = 5

Код расстояния

double dist(Point a, Point b) {
    long long dx = a.x - b.x;
    long long dy = a.y - b.y;

    return sqrt(dx * dx + dy * dy);
}

Если нужен точный квадрат расстояния, лучше не использовать sqrt.

Квадрат расстояния

Часто в задачах достаточно сравнить расстояния. Тогда можно сравнивать квадраты расстояний.

long long dist2(Point a, Point b) {
    long long dx = a.x - b.x;
    long long dy = a.y - b.y;

    return dx * dx + dy * dy;
}

Это лучше, потому что:

нет ошибки вещественных чисел
работает быстрее
не нужен sqrt

Скалярное произведение

Скалярное произведение двух векторов:

dot(a, b) = a.x * b.x + a.y * b.y

В C++:

long long dot(Point a, Point b) {
    return a.x * b.x + a.y * b.y;
}

Зачем нужен dot?

Скалярное произведение помогает понять угол между векторами.

dot > 0 → угол острый
dot = 0 → угол прямой
dot < 0 → угол тупой

Также dot используется для проекций и проверки перпендикулярности.

Проверка перпендикулярности

Если два вектора перпендикулярны, то их скалярное произведение равно 0.

if (dot(a, b) == 0) {
    cout << "perpendicular";
}

Например:

a = (1, 0)
b = (0, 1)

dot = 1 * 0 + 0 * 1 = 0

Векторное произведение

В 2D геометрии векторное произведение двух векторов:

cross(a, b) = a.x * b.y - a.y * b.x

В C++:

long long cross(Point a, Point b) {
    return a.x * b.y - a.y * b.x;
}

Зачем нужен cross?

cross показывает, в какую сторону поворачивает один вектор относительно другого.

cross > 0 → поворот налево
cross < 0 → поворот направо
cross = 0 → точки лежат на одной прямой

Это одна из самых важных операций в геометрии.

Ориентация трех точек

Для трех точек A, B, C нужно понять: точка C лежит слева или справа от направленного отрезка AB.

Считаем:

cross(B - A, C - A)

> 0 → C слева от AB
< 0 → C справа от AB
= 0 → A, B, C лежат на одной прямой

Код ориентации

long long orient(Point a, Point b, Point c) {
    return cross(b - a, c - a);
}

Использование:

long long val = orient(a, b, c);

if (val > 0) {
    cout << "left";
} else if (val < 0) {
    cout << "right";
} else {
    cout << "collinear";
}

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

Удвоенная площадь треугольника ABC:

abs(cross(B - A, C - A))

Значит обычная площадь:

abs(cross(B - A, C - A)) / 2

В C++:

double triangle_area(Point a, Point b, Point c) {
    return abs(cross(b - a, c - a)) / 2.0;
}

Точка на отрезке

Нужно проверить, лежит ли точка P на отрезке AB.

Нужно выполнить два условия:

1. A, B, P лежат на одной прямой
2. P находится внутри прямоугольника между A и B

То есть:

orient(A, B, P) = 0

Код: точка на отрезке

bool onSegment(Point a, Point b, Point p) {
    if (orient(a, b, p) != 0) {
        return false;
    }

    return min(a.x, b.x) <= p.x && p.x <= max(a.x, b.x) &&
           min(a.y, b.y) <= p.y && p.y <= max(a.y, b.y);
}

Пересечение двух отрезков

Даны два отрезка:

AB
CD

Нужно понять, пересекаются ли они.

Главная идея: точки C и D должны лежать по разные стороны от AB, а точки A и B — по разные стороны от CD.

Общий случай пересечения

Считаем ориентации:

orient(a, b, c)
orient(a, b, d)
orient(c, d, a)
orient(c, d, b)

Если знаки разные, то отрезки пересекаются.

Но нужно отдельно обработать случаи, когда точки лежат на одной прямой.

Код: пересечение отрезков

int sign(long long x) {
    if (x > 0) {
        return 1;
    }

    if (x < 0) {
        return -1;
    }

    return 0;
}

bool segmentsIntersect(Point a, Point b, Point c, Point d) {
    long long o1 = orient(a, b, c);
    long long o2 = orient(a, b, d);
    long long o3 = orient(c, d, a);
    long long o4 = orient(c, d, b);

    if (sign(o1) * sign(o2) < 0 && sign(o3) * sign(o4) < 0) {
        return true;
    }

    if (onSegment(a, b, c)) {
        return true;
    }

    if (onSegment(a, b, d)) {
        return true;
    }

    if (onSegment(c, d, a)) {
        return true;
    }

    if (onSegment(c, d, b)) {
        return true;
    }

    return false;
}

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

#include <bits/stdc++.h>
using namespace std;

struct Point {
    long long x;
    long long y;

    Point operator - (const Point &other) const {
        return {x - other.x, y - other.y};
    }
};

long long cross(Point a, Point b) {
    return a.x * b.y - a.y * b.x;
}

long long orient(Point a, Point b, Point c) {
    return cross(b - a, c - a);
}

int sign(long long x) {
    if (x > 0) {
        return 1;
    }

    if (x < 0) {
        return -1;
    }

    return 0;
}

bool onSegment(Point a, Point b, Point p) {
    if (orient(a, b, p) != 0) {
        return false;
    }

    return min(a.x, b.x) <= p.x && p.x <= max(a.x, b.x) &&
           min(a.y, b.y) <= p.y && p.y <= max(a.y, b.y);
}

bool segmentsIntersect(Point a, Point b, Point c, Point d) {
    long long o1 = orient(a, b, c);
    long long o2 = orient(a, b, d);
    long long o3 = orient(c, d, a);
    long long o4 = orient(c, d, b);

    if (sign(o1) * sign(o2) < 0 && sign(o3) * sign(o4) < 0) {
        return true;
    }

    if (onSegment(a, b, c)) {
        return true;
    }

    if (onSegment(a, b, d)) {
        return true;
    }

    if (onSegment(c, d, a)) {
        return true;
    }

    if (onSegment(c, d, b)) {
        return true;
    }

    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    Point a, b, c, d;

    cin >> a.x >> a.y;
    cin >> b.x >> b.y;
    cin >> c.x >> c.y;
    cin >> d.x >> d.y;

    if (segmentsIntersect(a, b, c, d)) {
        cout << "YES";
    } else {
        cout << "NO";
    }

    return 0;
}

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

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

Формула:

area2 = abs(sum(cross(p[i], p[i + 1])))

Это удвоенная площадь. Обычная площадь:

area = area2 / 2

Код: площадь многоугольника

long long polygon_area2(vector<Point> p) {
    int n = p.size();

    long long s = 0;

    for (int i = 0; i < n; i++) {
        Point a = p[i];
        Point b = p[(i + 1) % n];

        s += cross(a, b);
    }

    return abs(s);
}

Если нужно вывести обычную площадь:

long long area2 = polygon_area2(p);

if (area2 % 2 == 0) {
    cout << area2 / 2;
} else {
    cout << area2 / 2 << ".5";
}

Пример площади

Квадрат:

(0,0)
(2,0)
(2,2)
(0,2)

Его площадь:

Удвоенная площадь:

Выпуклый многоугольник

Выпуклый многоугольник — это многоугольник, где все повороты идут в одну сторону.

Проверка:

считаем orient для каждой тройки соседних точек
все ненулевые знаки должны быть одинаковыми

Код: проверка выпуклости

bool isConvex(vector<Point> p) {
    int n = p.size();

    int last = 0;

    for (int i = 0; i < n; i++) {
        Point a = p[i];
        Point b = p[(i + 1) % n];
        Point c = p[(i + 2) % n];

        int cur = sign(orient(a, b, c));

        if (cur == 0) {
            continue;
        }

        if (last != 0 && cur != last) {
            return false;
        }

        last = cur;
    }

    return true;
}

Точка внутри многоугольника

Для произвольного многоугольника можно использовать метод луча.

Идея:

пускаем луч из точки вправо
считаем, сколько раз он пересек стороны многоугольника
если количество нечетное → точка внутри
если четное → точка снаружи

Если точка лежит на границе, обычно это обрабатывается отдельно.

Код: точка внутри многоугольника

bool insidePolygon(vector<Point> p, Point q) {
    int n = p.size();
    bool inside = false;

    for (int i = 0; i < n; i++) {
        Point a = p[i];
        Point b = p[(i + 1) % n];

        if (onSegment(a, b, q)) {
            return true;
        }

        bool cond1 = (a.y > q.y) != (b.y > q.y);

        if (cond1) {
            double x = a.x + 1.0 * (b.x - a.x) * (q.y - a.y) / (b.y - a.y);

            if (x > q.x) {
                inside = !inside;
            }
        }
    }

    return inside;
}

Угол между векторами

Угол между векторами можно найти через скалярное произведение:

cos(angle) = dot(a, b) / (|a| * |b|)

Код:

double length(Point a) {
    return sqrt(a.x * a.x + a.y * a.y);
}

double angle(Point a, Point b) {
    double cosValue = dot(a, b) / (length(a) * length(b));

    cosValue = max(-1.0, min(1.0, cosValue));

    return acos(cosValue);
}

max/min нужны из-за возможной ошибки double.

Поворот точки

Чтобы повернуть точку (x, y) вокруг начала координат на угол angle:

newX = x * cos(angle) - y * sin(angle)
newY = x * sin(angle) + y * cos(angle)

Код:

struct DPoint {
    double x;
    double y;
};

DPoint rotatePoint(DPoint p, double angle) {
    double cs = cos(angle);
    double sn = sin(angle);

    return {
        p.x * cs - p.y * sn,
        p.x * sn + p.y * cs
    };
}

Целочисленная и вещественная геометрия

Тип	Когда использовать
long long	координаты целые, нужны точные сравнения
double	нужны углы, окружности, sqrt, sin, cos

Для ориентации, пересечения отрезков и площади лучше использовать long long, если координаты целые.

EPS для double

В double нельзя надежно сравнивать числа через ==. Нужно использовать маленькую погрешность EPS.

const double EPS = 1e-9;

int cmp(double x) {
    if (x > EPS) {
        return 1;
    }

    if (x < -EPS) {
        return -1;
    }

    return 0;
}

Если cmp(x) == 0, считаем число равным нулю.

Базовый шаблон геометрии

struct Point {
    long long x;
    long long y;

    Point operator + (const Point &other) const {
        return {x + other.x, y + other.y};
    }

    Point operator - (const Point &other) const {
        return {x - other.x, y - other.y};
    }
};

long long dot(Point a, Point b) {
    return a.x * b.x + a.y * b.y;
}

long long cross(Point a, Point b) {
    return a.x * b.y - a.y * b.x;
}

long long orient(Point a, Point b, Point c) {
    return cross(b - a, c - a);
}

long long dist2(Point a, Point b) {
    long long dx = a.x - b.x;
    long long dy = a.y - b.y;

    return dx * dx + dy * dy;
}

Типичные задачи

найти расстояние между точками
проверить, лежат ли точки на одной прямой
определить левый или правый поворот
проверить пересечение отрезков
найти площадь треугольника
найти площадь многоугольника
проверить, лежит ли точка внутри многоугольника
проверить выпуклость многоугольника

Типичные ошибки

Путать dot и cross
Забыть, что cross может быть отрицательным
Использовать int, когда координаты большие
Сравнивать double через ==
Забыть обработать случай, когда точка лежит на отрезке
Не обработать коллинеарные отрезки
В площади многоугольника забыть последнее ребро от p[n-1] к p[0]
Путать площадь и удвоенную площадь

Асимптотика

Операция	Время
Расстояние между двумя точками	O(1)
dot / cross	O(1)
Ориентация трех точек	O(1)
Пересечение двух отрезков	O(1)
Площадь многоугольника	O(n)
Точка внутри многоугольника	O(n)
Проверка выпуклости	O(n)

Когда что использовать?

нужно расстояние → dist или dist2
нужно проверить угол → dot
нужно направление поворота → cross / orient
нужно проверить коллинеарность → orient == 0
нужно пересечение отрезков → orient + onSegment
нужна площадь → сумма cross
есть double → сравнивай через EPS

Главное запомнить

точка = (x, y)
вектор AB = B - A
dot показывает угол
cross показывает поворот
orient(a,b,c) показывает положение точки c относительно ab
площадь считается через cross
пересечение отрезков проверяется через orient