Шаблон по геометрии

Геометрия пишется поверх заготовки. Написать её один раз и понимать целиком — половина дела: дальше задачи сводятся к вызову готовых функций.

Структура

using ld = long double;

struct Point {
    ld x = 0, y = 0;

    Point() = default;
    Point(ld x, ld y) : x(x), y(y) {}
    Point(Point a, Point b) : x(b.x - a.x), y(b.y - a.y) {}   // вектор из a в b

    Point operator+(Point p) const { return {x + p.x, y + p.y}; }
    Point operator-(Point p) const { return {x - p.x, y - p.y}; }
    Point operator*(ld k) const { return {x * k, y * k}; }

    ld operator*(Point p) const { return x * p.x + y * p.y; }   // скалярное
    ld operator%(Point p) const { return x * p.y - y * p.x; }   // векторное

    ld len2() const { return x * x + y * y; }
    ld len()  const { return sqrtl(len2()); }
};

ld dist(Point a, Point b) { return Point(a, b).len(); }

Одна структура и для точки, и для вектора — они и так одно и то же. Ссылки в аргументах не нужны: два числа копируются дешевле, чем разыменовывается ссылка.

Почему * и %, а не функции. У этих операторов одинаковый приоритет, и выражения вроде a % b == 0 пишутся без лишних скобок. Если взять ^ для векторного, придётся писать (a ^ b) == 0: у побитового исключающего «или» приоритет ниже, чем у сравнения, и a ^ b == 0 означает совсем не то.

Ввод и вывод

istream& operator>>(istream& in, Point& p) { return in >> p.x >> p.y; }
ostream& operator<<(ostream& out, const Point& p) { return out << p.x << ' ' << p.y; }

Поток берётся и возвращается по ссылке, чтобы работали цепочки cin >> a >> b. Подробнее — в статье про свои структуры.

Без этих двух строк каждое чтение точки превращается в cin >> p.x >> p.y, а ошибка компиляции при попытке cin >> p занимает под двести строк, из которых полезна первая.

Конструктор, который стоит часов

Самая коварная ловушка всего раздела.

Соблазн написать конструктор со значениями по умолчанию:

Point(ld x = 0, ld y = 0) : x(x), y(y) {}   // так не надо

Выглядит удобно: Point(), Point(5) и Point(2, 3) — всё работает. Проблема в том, что такой конструктор позволяет компилятору неявно превращать число в точку.

Теперь представьте, что вы забыли написать operator* для умножения на число. Строка

v = v * 2;

не даст ошибки компиляции. Компилятор превратит 2 в Point(2, 0) и вызовет векторное произведение — то есть посчитает число, а потом превратит его обратно в точку. Результат — тихо неверный ответ.

Найти такое чтением кода почти невозможно. Есть два способа не попасться:

explicit Point(ld x = 0, ld y = 0) : x(x), y(y) {}   // либо так
Point(ld x, ld y) : x(x), y(y) {}                    // либо без умолчаний

explicit запрещает неявное преобразование: Point p = 1; перестаёт компилироваться, а Point p(1) работает. Второй вариант проще: без значений по умолчанию конструктор от одного аргумента просто не существует.

Если сомневаетесь — берите второй. Он короче и не требует помнить, что делает explicit.

Целые или вещественные

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

using ll = long long;   // вместо ld

При этом произведения обязательно long long: при координатах до $10^9$ они доходят до $2 \cdot 10^{18}$.

Переходить к long double стоит только там, где без деления или корня действительно не обойтись, — и лучше в отдельной функции, а не во всём шаблоне.

Типичное разделение: сравнения, ориентации, площади и принадлежности — в целых; расстояния, углы и точки пересечения — в вещественных.

Что ещё положить в шаблон

Минимальный полезный набор поверх структуры:

• dist(a, b) — расстояние;
• angle(a, b) — угол через atan2;
• сравнения с эпсилоном (см. следующую статью);
• проверки принадлежности точки прямой, лучу, отрезку;
• пересечение отрезков.

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