Chapter 119

Refactoring: Monotone Chain

Graham scan uses polar angles (floating-point division — slow, imprecise). Andrew's monotone chain sorts by (x, y) and builds the upper and lower hulls separately. Integer-only, faster, no angle computation.

Before: Graham Scan (angle-based)

C++ — angle sort

// Requires atan2 or cross-product comparator
// Floating point inaccuracies possible

After: Andrew's Monotone Chain

C++ — monotone chain (Andrew's algorithm)

vector convex_hull(vector pts) {
    sort(pts.begin(), pts.end(), [](Point a, Point b) {
        return a.x < b.x || (a.x == b.x && a.y < b.y);
    });

    vector hull;
    for (int phase = 0; phase < 2; phase++) {
        int start = hull.size();
        for (auto& p : pts) {
            while (hull.size() >= start + 2 &&
                   orient(hull[hull.size()-2], hull.back(), p) <= 0)
                hull.pop_back();
            hull.push_back(p);
        }
        hull.pop_back();  // remove duplicate endpoint
        reverse(pts.begin(), pts.end());
    }
    return hull;
}

// O(N log N) sorting + O(N) hull building.
// Integer-only — no floating point needed.