Векторы | kz-maxx

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

Вектор — это объект, у которого есть направление и длина.

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

v = (x, y)

Например:

v = (3, 4)

Это значит, что вектор идет на 3 вправо и на 4 вверх.

Вектор между двумя точками

Если есть две точки:

A = (x1, y1)
B = (x2, y2)

То вектор из A в B равен:

AB = (x2 - x1, y2 - y1)

Пример:

A = (2, 1)
B = (7, 4)

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

Структура для точки и вектора

В задачах по геометрии точку и вектор удобно хранить одинаково.

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

Если 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 operator * (long long k) const {
        return {x * k, y * k};
    }
};

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

Point c = a + b;
Point v = b - a;
Point t = v * 3;

Сложение векторов

Если:

a = (x1, y1)
b = (x2, y2)

Тогда:

a + b = (x1 + x2, y1 + y2)

Пример:

(2, 3) + (5, 1) = (7, 4)

Вычитание векторов

Если:

a = (x1, y1)
b = (x2, y2)

Тогда:

a - b = (x1 - x2, y1 - y2)

Пример:

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

Умножение вектора на число

Если вектор умножить на число, его координаты тоже умножаются.

k * (x, y) = (k * x, k * y)

Пример:

3 * (2, 5) = (6, 15)

Если k положительное, направление сохраняется. Если k отрицательное, направление меняется на противоположное.

Длина вектора

Длина вектора v = (x, y):

|v| = sqrt(x^2 + y^2)

Пример:

v = (3, 4)

|v| = sqrt(3^2 + 4^2) = 5

Код длины вектора

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

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

Квадрат длины

Квадрат длины:

|v|^2 = x^2 + y^2

Код:

long long length2(Point v) {
    return v.x * v.x + v.y * v.y;
}

Это удобно, потому что:

нет sqrt
нет ошибки double
работает быстрее

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

Расстояние между точками A и B — это длина вектора B - A.

double dist(Point a, Point b) {
    return length(b - a);
}

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

long long dist2(Point a, Point b) {
    return length2(b - a);
}

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

Скалярное произведение, или dot product:

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

Код:

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

Что показывает dot?

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

dot(a, b) > 0 → угол острый
dot(a, b) = 0 → угол прямой
dot(a, b) < 0 → угол тупой

Поэтому dot часто используют для проверки перпендикулярности.

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

Два вектора перпендикулярны, если:

dot(a, b) = 0

Код:

bool perpendicular(Point a, Point b) {
    return dot(a, b) == 0;
}

Пример:

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

dot(a, b) = 0

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

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

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

Код:

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

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

    return acos(value);
}

max/min нужны, чтобы из-за ошибки double значение не стало чуть больше 1 или чуть меньше -1.

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

В 2D геометрии векторное произведение, или cross product:

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

Код:

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

Что показывает cross?

Cross показывает направление поворота от первого вектора ко второму.

cross(a, b) > 0 → b находится слева от a
cross(a, b) < 0 → b находится справа от a
cross(a, b) = 0 → векторы лежат на одной прямой

Это самая важная операция для задач на повороты, ориентацию и пересечение отрезков.

Коллинеарные векторы

Два вектора называются коллинеарными, если они лежат на одной прямой.

Условие:

cross(a, b) = 0

Код:

bool collinear(Point a, Point b) {
    return cross(a, b) == 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";
}

Площадь через cross

Модуль cross равен площади параллелограмма на двух векторах.

area_parallelogram = abs(cross(a, b))

Площадь треугольника в 2 раза меньше:

area_triangle = abs(cross(a, b)) / 2

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

Для точек A, B, C:

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

Это удвоенная площадь.

Код:

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

Поворот вектора на 90 градусов

Если вектор:

v = (x, y)

Тогда поворот на 90 градусов против часовой стрелки:

(-y, x)

Поворот на 90 градусов по часовой стрелке:

(y, -x)

Код поворота на 90 градусов

Point rotate90Left(Point v) {
    return {-v.y, v.x};
}

Point rotate90Right(Point v) {
    return {v.y, -v.x};
}

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

Поворот на любой угол

Если нужно повернуть вектор на угол angle, используем sin и cos.

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

Код:

struct DPoint {
    double x;
    double y;
};

DPoint rotate(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
    };
}

Угол в C++ для sin, cos, acos задается в радианах.

Проекция вектора

Проекция вектора a на вектор b показывает, какая часть a направлена вдоль b.

Длина проекции:

dot(a, b) / |b|

Если нужна точная формула, обычно используют double.

Сортировка по полярному углу

Иногда нужно отсортировать точки или векторы по углу относительно начала координат.

Простой способ — использовать atan2:

double getAngle(Point p) {
    return atan2(p.y, p.x);
}

Сортировка:

sort(a.begin(), a.end(), [](Point p1, Point p2) {
    return atan2(p1.y, p1.x) < atan2(p2.y, p2.x);
});

atan2 возвращает угол в радианах от -pi до pi.

Нормализация вектора

Иногда нужно привести вектор к единичной длине. Это называется нормализация.

unit = v / |v|

Для этого нужен double:

DPoint normalize(DPoint v) {
    double len = sqrt(v.x * v.x + v.y * v.y);

    return {v.x / len, v.y / len};
}

Нулевой вектор нормализовать нельзя, потому что его длина равна 0.

Нулевой вектор

Нулевой вектор:

(0, 0)

У него длина равна 0. У него нет направления.

Проверка:

bool isZero(Point v) {
    return v.x == 0 && v.y == 0;
}

Полный базовый шаблон

#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};
    }

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

    Point operator * (long long k) const {
        return {x * k, y * k};
    }
};

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 length2(Point v) {
    return v.x * v.x + v.y * v.y;
}

double length(Point v) {
    return sqrt(length2(v));
}

long long dist2(Point a, Point b) {
    return length2(b - a);
}

double dist(Point a, Point b) {
    return length(b - a);
}

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

    Point a, b;
    cin >> a.x >> a.y;
    cin >> b.x >> b.y;

    Point v = b - a;

    cout << v.x << ' ' << v.y << '\n';
    cout << length(v) << '\n';

    return 0;
}

Пример

Input

2 1
7 4

Output

5 3
5.83095

Здесь:

A = (2, 1)
B = (7, 4)

AB = (5, 3)

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

нужно проверить перпендикулярность → dot == 0
нужно понять острый или тупой угол → знак dot
нужно найти угол → acos через dot
нужна проекция → dot
нужно сравнить направления → dot

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

нужно проверить поворот → cross
нужно проверить коллинеарность → cross == 0
нужно найти площадь → abs(cross)
нужно проверить пересечение отрезков → orient через cross
нужно построить convex hull → cross

long long или double?

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

Если координаты целые, то dot, cross и orient лучше считать через long long.

EPS для double

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

const double EPS = 1e-9;

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

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

    return 0;
}

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

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

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

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

Путать точку и вектор
Писать A - B вместо B - A для вектора AB
Путать dot и cross
Думать, что cross всегда положительный
Использовать int при больших координатах
Брать sqrt, когда можно сравнивать length2
Сравнивать double через ==
Нормализовать нулевой вектор

Асимптотика

Операция	Время
Сложение векторов	O(1)
Вычитание векторов	O(1)
Длина вектора	O(1)
dot	O(1)
cross	O(1)
orientation	O(1)
Сортировка по углу	O(n log n)

Короткий шаблон

struct Point {
    long long x;
    long long 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 length2(Point v) {
    return v.x * v.x + v.y * v.y;
}

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

вектор = направление + длина
AB = B - A
length = sqrt(x² + y²)
dot показывает угол
cross показывает поворот
cross == 0 → коллинеарность
dot == 0 → перпендикулярность