Computational Geometry

The cross product, polygon area and the convex hull.

Almost all contest geometry is built on one tool — the cross product: cross(O, A, B) = (A - O) × (B - O) = (Ax-Ox)(By-Oy) - (Ay-Oy)(Bx-Ox) Its sign tells you which way the polyline O→A→B turns: plus — counterclockwise, minus — clockwise, zero — the three points are collinear. And its absolute value equals twice the area of triangle OAB. The first application — the area of any polygon (the "shoelace formula"): the sum of cross products of consecutive vertices.

Try it yourself — the code is editable

Input (sample — feel free to edit)

Polygon area. Enter: 4, then the vertices along the contour: 0 0, 4 0, 4 3, 0 3

The 4×3 rectangle gives 12. Notice: everything is computed in INTEGERS — we store twice the area and divide only when printing. The golden rule of geometry: stay in integers as long as possible; double with its rounding errors is the source of the most treacherous bugs. The second classic — the convex hull: the smallest convex polygon containing all the points. Andrew's monotone chain algorithm: sort the points by x, build the lower chain left to right, discarding points that make the "wrong" turn, then the upper chain right to left. O(n log n) for the sorting.

Try it yourself — the code is editable

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

Input (sample — feel free to edit)

The convex hull. Enter: 6, then the points: 0 0, 2 0, 1 1, 2 2, 0 2, 1 -1

On the example the interior point (1,1) disappears, leaving the five hull vertices in counterclockwise order. The condition cross <= 0 also discards points on a straight line; replace it with < 0 if collinear points must be kept. Task: given the finished hull, compute its area with the shoelace formula — the lesson's two topics join into one solution. Mark the lesson as completed — you have walked the entire competitive path! What remains is practice: solve problems, compete, and come back to the lessons as a reference. Good luck!