guest@itl:~/home/geometry$
templates/convex-hull-andrew.cpp
compilable
$cat templates/convex-hull-andrew

Convex Hull (Andrew's)

Andrew's monotone chain algorithm for convex hull in O(n log n).

[Geometry]|
Jul 9, 2026
|explanatory_notes.md|
#convex-hull#geometry#monotone-chain#andrew
Log in to track progress, save custom versions, and organize into collections.Log In
$cat source_code/
cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct Point {
    ll x, y;
    Point(ll x = 0, ll y = 0) : x(x), y(y) {}
    Point operator-(const Point &p) const { return {x - p.x, y - p.y}; }
    ll cross(const Point &p) const { return x * p.y - y * p.x; }
    ll dist(const Point &p) const { return (x-p.x)*(x-p.x) + (y-p.y)*(y-p.y); }
    bool operator<(const Point &p) const { return x < p.x || (x == p.x && y < p.y); }
    friend istream &operator>>(istream &in, Point &p) { return in >> p.x >> p.y; }
};

vector<Point> convexHull(vector<Point> pts, bool includeCollinear = false) {
    int n = pts.size();
    if (n < 2) return pts;
    sort(pts.begin(), pts.end());
    pts.erase(unique(pts.begin(), pts.end(), [](const Point &a, const Point &b) {
        return a.x == b.x && a.y == b.y;
    }), pts.end());
    n = pts.size();
    if (n < 2) return pts;

    vector<Point> hull;
    auto check = [&](const Point &p) -> bool {
        ll cr = (hull.back() - hull[hull.size()-2]).cross(p - hull.back());
        return includeCollinear ? cr < 0 : cr <= 0;
    };

    for (int i = 0; i < n; i++) {
        while (hull.size() >= 2 && check(pts[i])) hull.pop_back();
        hull.push_back(pts[i]);
    }
    int lower = hull.size();
    for (int i = n - 2; i >= 0; i--) {
        while ((int)hull.size() > lower && check(pts[i])) hull.pop_back();
        hull.push_back(pts[i]);
    }
    hull.pop_back();
    return hull;
}
42 linesutf-8
$cat explanation_notes.md
notes_viewer --renderedmarkdown (math enabled)

Convex Hull — Andrew's Monotone Chain

Compute the convex hull of a set of 2D points in O(nlog⁡n)O(n \log n).

How It Works

  • Sort points lexicographically by (x,y)(x, y)

  • Build lower hull left-to-right: for each point, remove previous points that make a non-left (clockwise) turn

  • Build upper hull right-to-left with the same logic

  • Concatenate both halves (remove duplicate endpoints)

    • Orientation Test

    The cross product cross(B−A,C−A)\text{cross}(B - A, C - A) determines turn direction:

  • >0> 0 — counter-clockwise (left turn)

  • =0= 0 — collinear

  • <0< 0 — clockwise (right turn)

    • When to Use

  • Computing convex hull of a point set

  • Farthest pair of points (rotating calipers on hull)

  • Checking if a point is inside a convex polygon

  • Minimum enclosing shapes

    • Notes

  • Set includeCollinear = true to keep collinear points on the hull boundary

  • The Point struct is included — also available standalone in the Geometry Points template

  • Hull vertices are in counter-clockwise order

    • Complexity

  • Time — O(nlog⁡n)O(n \log n) dominated by sorting

  • Space — O(n)O(n)