Точки и векторы - Алгоритмика
Точки и векторы

Точки и векторы

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

Точка $\simeq$ вектор. Так как оба задаются просто парой чисел, можно считать их одним и тем же классом объектов и сопоставлять каждой точке её радиус-вектор — вектор из начала координат, ведущий в эту точку.

Как их хранить

Создадим класс, который будет отвечать за все операции с векторами. В C++ есть два способа это сделать: через struct и через class. Их основное отличие в том, что по умолчанию в class все поля приватные — к ним нет прямого доступа снаружи. Это нужно для дополнительной защиты, чтобы в крупных проектах никто случайно ничего не поломал, но на олимпиадах это не очень актуально, поэтому объявим struct. По принятой в математике и физике нотации, назовём его r. Если хотите, можете назвать его point, pt, vec — как угодно.

struct r {
    int x, y;
    r() {}
    r(int x, int y) : x(x), y(y) {}
};

Функция r внутри класса или структуры с таким же именем вызывается при инициализации объекта. Её называют конструктором, и её можно указывать разную для разных входных аргументов. Здесь r()вернёт точку с неопределенными (какие оказались в памяти в тот момент) координатами, а r(x, y) вернет точку с координатами $(x, y)$.

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

Операции над векторами

Давайте напишем функцию, которая принимает вектор и что-то с ним делает. Например, считает длину:

double len(r a) { return sqrt(a.x * a.x + a.y * a.y); }
// или:
double len(r a) { return hypot(a.x, a.y); }

Это подход языка C. В C++ удобнее определить метод:

double r::len() { return hypot(x, y); }
// (альтернативно можно добавить функцию len() внутри самой структуры)

Помимо чуть более чистой реализации, есть ещё разница в синтаксисе вызова: len(a) или a.len().

Операторы

В C++ можно перегружать почти все стандартные операторы, например, +, -, * и т. д.

Переопределим для будущих нужд + и -:

r operator+(r a, r b) { return {a.x + b.x, a.y + b.y}; }
r operator-(r a, r b) { return {a.x - b.x, a.y - b.y}; }

Как вы думаете, как на самом деле работает cin >> x? Это тоже перегрузка оператора: >>. Делается это так:

istream& operator>>(istream &in, r &p) { 
    in >> p.x >> p.y;
    return in;
}

ostream& operator<<(ostream &out, r &p) { 
    out << p.x << " " << p.y << endl;
    return out;            
}

Углы и повороты

Для подсчета угла вектора относительно оси $x$ можно вспомнить тригонометрический круг и посчитать арктангенс от $\frac{y}{x}$.

В C++ и Python есть функция atan2, которая делает это немного быстрее и точнее деления и арктангенса:

double r::angle() {
    return atan2(y, x);
}

Вернется число от в промежутке $[-\pi, +\pi]$, в радианах. Для градусов нужно домножить на $\frac{180}{\pi}$.

Поворот вектора на угол $\alpha$ задаётся следующим матричным уравнением:

$$ Rot_{\alpha}(\overline{(x, y)}) = \begin{pmatrix} \cos(\alpha) & -\sin(\alpha) \\ \sin(\alpha) & \cos(\alpha) \end{pmatrix} \begin{pmatrix} x \\ y \end{pmatrix} = \begin{pmatrix} \cos(\alpha) \cdot x - \sin(\alpha) \cdot y \\ \sin(\alpha) \cdot x + \cos(\alpha) \cdot y \end{pmatrix} $$

В частности, $Rot_{90^{\circ}} (\overline{(x, y)}) = \overline{(-y,x)}$.

Для ноулайферов: комплексные числа

Можно всё это делать используя std::complex.