Convex Hull (Monotone Chain)

O(n log n)

Convex hull of a point set: sort once, then build the lower and upper chains with a cross-product stack. All integer arithmetic, no floating point, no angle sorting. Returned counter-clockwise with collinear points dropped (change the <= to < to keep them).

// use it on

CSES: Convex Hull ↗

Output the hull vertices, which is the template verbatim. Watch for duplicate input points.

// the code

typedef long long ll;
typedef pair<ll, ll> pt;

ll cross(pt O, pt A, pt B) {
    return (A.first - O.first) * (B.second - O.second) -
           (A.second - O.second) * (B.first - O.first);
}

vector<pt> convex_hull(vector<pt> pts) {  // counter-clockwise
    sort(pts.begin(), pts.end());
    pts.erase(unique(pts.begin(), pts.end()), pts.end());
    if (pts.size() < 3) return pts;
    vector<pt> hull;
    for (int pass = 0; pass < 2; pass++) {  // lower, then upper chain
        size_t start = hull.size();
        for (pt& p : pts) {
            while (hull.size() >= start + 2 &&
                   cross(hull[hull.size() - 2], hull.back(), p) <= 0)
                hull.pop_back();
            hull.push_back(p);
        }
        hull.pop_back();
        reverse(pts.begin(), pts.end());
    }
    return hull;
}

// more geometry

Geometry Primitives Closest Pair of Points