Эсептөө геометриясы

Вектордук көбөйтүндү, көп бурчтуктун аянты жана томпок кабык.

Дээрлик бүт олимпиадалык геометрия бир куралга курулат — вектордук (кыйшык) көбөйтүндүгө: 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 менен алмаштырыңыз. Тапшырма: даяр кабык боюнча анын аянтын бүчүлүк формуласы менен эсептеңиз — сабактын эки темасы бир чечимде биригет. Сабакты өттүм деп белгилеңиз — сиз олимпиадачынын бүт жолун өттүңүз! Мындан ары — практика: маселелерди чечиңиз, мелдештерге катышыңыз жана сабактарга маалымдама катары кайрылып туруңуз. Ийгилик!