Вычислительная геометрия

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

Почти вся олимпиадная геометрия строится на одном инструменте — векторном (косом) произведении: cross(O, A, B) = (A - O) × (B - O) = (Ax-Ox)(By-Oy) - (Ay-Oy)(Bx-Ox) Его знак говорит, куда поворачивает ломаная O→A→B: плюс — против часовой стрелки, минус — по часовой, ноль — три точки на одной прямой. А модуль равен удвоенной площади треугольника OAB. Первое применение — площадь любого многоугольника («формула шнурков»): сумма косых произведений последовательных вершин.

Попробуйте сами — код можно менять

Входные данные (пример — можно менять)

Площадь многоугольника. Введите: 4, затем вершины по контуру: 0 0, 4 0, 4 3, 0 3

Прямоугольник 4×3 даёт 12. Заметьте: всё считается в ЦЕЛЫХ числах — храним удвоенную площадь и делим только при выводе. Золотое правило геометрии: оставайтесь в целых числах как можно дольше, double с его погрешностями — источник самых коварных багов. Вторая классика — выпуклая оболочка: минимальный выпуклый многоугольник, содержащий все точки. Алгоритм Эндрю (monotone chain): сортируем точки по x, строим нижнюю цепочку слева направо, выкидывая точки, дающие «не тот» поворот, затем верхнюю — справа налево. O(n log n) на сортировку.

Попробуйте сами — код можно менять

#include <iostream>
#include <vector>
#include <algorithm>

struct Pt {
    long long x, y;
};

long long cross(const Pt &o, const Pt &a, const Pt &b) {
    return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x);
}

int main() {
    int n;
    std::cin >> n;
    std::vector<Pt> p(n);
    for (auto &pt : p) std::cin >> pt.x >> pt.y;

std::sort(p.begin(), p.end(), [](const Pt &a, const Pt &b) {
        return a.x < b.x || (a.x == b.x && a.y < b.y);
    });

std::vector<Pt> hull;
    for (int pass = 0; pass < 2; pass++) {
        int start = hull.size();
        for (auto &pt : p) {
            while ((int)hull.size() >= start + 2 &&
                   cross(hull[hull.size() - 2], hull[hull.size() - 1], pt) <= 0) {
                hull.pop_back();
            }
            hull.push_back(pt);
        }
        hull.pop_back(); // крайняя точка попадёт в начало следующей цепочки
        std::reverse(p.begin(), p.end());
    }

std::cout << "Вершины выпуклой оболочки:\n";
    for (auto &pt : hull) std::cout << pt.x << " " << pt.y << "\n";
    return 0;
}

Входные данные (пример — можно менять)

Выпуклая оболочка. Введите: 6, затем точки: 0 0, 2 0, 1 1, 2 2, 0 2, 1 -1

На примере внутренняя точка (1,1) исчезает, остаются пять вершин оболочки в порядке обхода против часовой стрелки. Условие cross <= 0 выбрасывает и точки на прямой; замените на < 0, если коллинеарные точки нужно оставлять. Задание: по готовой оболочке посчитайте её площадь формулой шнурков — две темы урока соединятся в одно решение. Отметьте урок пройденным — вы прошли весь путь олимпиадника! Дальше — практика: решайте задачи, участвуйте в соревнованиях и возвращайтесь к урокам как к справочнику. Удачи!