Convex Hull: Graham Scan

C++ — Graham scan (naive angle sort)

vector graham_scan(vector& pts) {
    // Find lowest point (smallest y, then x)
    swap(pts[0], *min_element(pts.begin(), pts.end(), [](Point a, Point b) {
        return a.y < b.y || (a.y == b.y && a.x < b.x);
    }));

    // Sort by polar angle from pts[0]
    sort(pts.begin() + 1, pts.end(), [&](Point a, Point b) {
        double o = orient(pts[0], a, b);
        if (o == 0) return norm2({a.x-pts[0].x, a.y-pts[0].y})
                         < norm2({b.x-pts[0].x, b.y-pts[0].y});
        return o > 0;
    });

    vector hull;
    for (auto& p : pts) {
        while (hull.size() >= 2 && orient(hull[hull.size()-2], hull.back(), p) <= 0)
            hull.pop_back();
        hull.push_back(p);
    }
    return hull;
}

// O(N log N). Uses floating-point angle comparison — use cross product instead of atan2.