guest@cp-base:~/home/geometry$
templates/2d-geometry.cpp
compilable
$cat templates/2d-geometry

2D Geometry

Complete 2D computational geometry toolkit: points, lines, segments, polygons with intersection, area, and point-in-polygon.

[Geometry]|
Jul 9, 2026
|explanatory_notes.md|
#geometry#2d#line-intersection#polygon#point-in-polygon
Log in to track progress, save custom versions, and organize into collections.Log In
$cat source_code/
cpp
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
const ld EPS = 1e-9L;

using T = ld;
using pt = complex<T>;
#define x real()
#define y imag()

int sgn(T val) { return (T(0) < val) - (val < T(0)); }
T sq(pt p) { return p.x * p.x + p.y * p.y; }
pt perp(pt p) { return {-p.y, p.x}; }
T dot(pt v, pt w) { return v.x * w.x + v.y * w.y; }
T cross(pt v, pt w) { return v.x * w.y - v.y * w.x; }
T orient(pt a, pt b, pt c) { return cross(b - a, c - a); }

struct line {
    pt v; T c;
    line(pt v, T c) : v(v), c(c) {}
    line(T a, T b, T _c) : v(b, -a), c(_c) {}
    line(pt p, pt q) : v(q - p), c(cross(v, p)) {}
    T side(pt p) { return cross(v, p) - c; }
    ld dist(pt p) { return fabsl(side(p)) / abs(v); }
    pt proj(pt p) { return p - perp(v) * side(p) / sq(v); }
    pt refl(pt p) { return p - perp(v) * (T)2.0L * side(p) / sq(v); }
};

bool lineIntersect(line l1, line l2, pt &out) {
    T d = cross(l1.v, l2.v);
    if (fabsl(d) <= EPS) return false;
    out = (l2.v * l1.c - l1.v * l2.c) / d;
    return true;
}

bool onSegment(pt a, pt b, pt p) {
    return fabsl(orient(a, b, p)) <= EPS && dot(a - p, b - p) <= EPS;
}

bool properInter(pt a, pt b, pt c, pt d, pt &out) {
    T oa = orient(c, d, a), ob = orient(c, d, b);
    T oc = orient(a, b, c), od = orient(a, b, d);
    if (sgn(oa) * sgn(ob) < 0 && sgn(oc) * sgn(od) < 0) {
        out = (a * ob - b * oa) / (ob - oa);
        return true;
    }
    return false;
}

ld segPoint(pt a, pt b, pt p) {
    if (a != b && dot(p - a, b - a) >= 0 && dot(p - b, a - b) >= 0)
        return line(a, b).dist(p);
    return min(abs(p - a), abs(p - b));
}

bool isConvex(vector<pt> &p) {
    bool hasPos = false, hasNeg = false;
    int n = p.size();
    for (int i = 0; i < n; i++) {
        int o = sgn(orient(p[i], p[(i+1)%n], p[(i+2)%n]));
        if (o > 0) hasPos = true;
        if (o < 0) hasNeg = true;
    }
    return !(hasPos && hasNeg);
}

ld areaTriangle(pt a, pt b, pt c) {
    return fabsl(cross(b - a, c - a)) / 2.0L;
}

ld areaPolygon(vector<pt> &p) {
    ld area = 0;
    int n = p.size();
    for (int i = 0; i < n; i++)
        area += cross(p[i], p[(i+1)%n]);
    return fabsl(area) / 2.0L;
}

bool inPolygon(vector<pt> &p, pt a, bool strict = true) {
    int cnt = 0, n = p.size();
    for (int i = 0; i < n; i++) {
        if (onSegment(p[i], p[(i+1)%n], a)) return !strict;
        bool above = (p[(i+1)%n].y >= a.y) - (p[i].y >= a.y);
        cnt += above * orient(a, p[i], p[(i+1)%n]) > 0;
    }
    return cnt & 1;
}
88 linesutf-8
$cat explanation_notes.md
notes_viewer --renderedmarkdown (math enabled)

2D Geometry Toolkit

Core 2D geometry primitives using complex as the point type.

Primitives

  • sgn(val) — sign function (−1-1, 00, +1+1)

  • dot / cross / orient — fundamental geometric operations

  • perp(p) — 90° CCW rotation

    • Line

    Represented as direction vector vv and scalar cc where cross(v,p)=c\text{cross}(v, p) = c for points on the line.

  • Construct from: direction + constant, coefficients (a,b,c)(a, b, c), or two points

  • side(p) — signed distance indicator (positive = left, negative = right)

  • dist(p) — perpendicular distance from point to line

  • proj(p) — orthogonal projection onto line

  • refl(p) — reflection across line

    • Segment Operations

  • onSegment(a, b, p) — is point pp on segment ab‾\overline{ab}?

  • properInter(a, b, c, d) — proper intersection of segments ab‾\overline{ab} and cd‾\overline{cd}

  • segPoint(a, b, p) — minimum distance from segment to point

    • Polygon Operations

  • isConvex(p) — convexity check

  • areaTriangle / areaPolygon — area via cross product / shoelace formula

  • inPolygon(p, a) — ray casting point-in-polygon test (strict/non-strict boundary)

    • When to Use

  • Any geometry problem needing lines, segments, or polygon queries

  • Line intersection, point-in-polygon, area computation

  • For convex hull, use the dedicated Convex Hull template

    • Complexity

  • All individual operations — O(1)O(1)

  • isConvex / areaPolygon / inPolygon — O(n)O(n)