Geometry Primitives

O(1) per operation

The integer building blocks under every geometry problem: cross and dot products, orientation tests, exact segment intersection, and twice the signed polygon area. All long long arithmetic, so nothing here can suffer floating-point error.

// use it on

CSES: Point in Polygon ↗

Boundary cases fall to seg_intersect / collinearity checks; inside vs outside comes from a ray-crossing count built on these same primitives (see also CSES 2190 and 2191).

// the code

typedef long long ll;
struct P {
    ll x, y;
    P operator-(P o) const { return {x - o.x, y - o.y}; }
    ll cross(P o) const { return x * o.y - y * o.x; }
    ll dot(P o) const { return x * o.x + y * o.y; }
};

// > 0: a-b-c turns left; < 0: right; == 0: collinear
ll orient(P a, P b, P c) { return (b - a).cross(c - a); }

int sgn(ll v) { return (v > 0) - (v < 0); }

// do segments a-b and c-d intersect (touching counts)?
bool seg_intersect(P a, P b, P c, P d) {
    ll d1 = orient(c, d, a), d2 = orient(c, d, b);
    ll d3 = orient(a, b, c), d4 = orient(a, b, d);
    if (sgn(d1) != sgn(d2) && sgn(d3) != sgn(d4)) return true;
    auto on = [](P p, P q, P r) {  // r on segment p-q, collinear known
        return min(p.x, q.x) <= r.x && r.x <= max(p.x, q.x) &&
               min(p.y, q.y) <= r.y && r.y <= max(p.y, q.y);
    };
    if (d1 == 0 && on(c, d, a)) return true;
    if (d2 == 0 && on(c, d, b)) return true;
    if (d3 == 0 && on(a, b, c)) return true;
    if (d4 == 0 && on(a, b, d)) return true;
    return false;
}

// twice the signed area (positive if counter-clockwise)
ll area2(vector<P>& poly) {
    ll s = 0;
    int n = poly.size();
    for (int i = 0; i < n; i++) s += poly[i].cross(poly[(i + 1) % n]);
    return s;
}

// more geometry

Convex Hull (Monotone Chain)Closest Pair of Points