AntInLoop

Convex Hull (Andrew's Monotone Chain)

Andrew's Monotone Chain computes the Convex Hull of n 2D points in O(n log n) time using integer cross products, avoiding trigonometry and floating-point precision errors.

Difficulty: Hard · Interactive Visualizer · C++ / Python / Java / JS Code

Convex Hull (Andrew's Monotone Chain)

The Convex Hull of a set of 2D points is the smallest convex polygon enclosing all points (imagine stretching a rubber band around pegs). Andrew's Monotone Chain sorts points lexicographically by (x, y) and builds the lower hull and upper hull in two linear passes using only integer cross products—making it cleaner and more numerically robust than polar-angle Graham Scan!

At a Glance

| Property | Value |

| :--- | :---: |

| Time Complexity | $O(n \log n)$ (sorting) + $O(n)$ (hull scan) |

| Auxiliary Space | $O(n)$ |

| Orientation Test | $\text{cross}(O, A, B) = (A_x - O_x)(B_y - O_y) - (A_y - O_y)(B_x - O_x)$ (> 0 CCW, < 0 CW, 0 collinear) |

---

Practice Problems

Intermediate

1. Andrew's Monotone Chain Convex Hull (CCW Order)

Return the vertices of the Convex Hull in counter-clockwise order in $O(n \log n)$ time.

Approach: Sort by (x, y), deduplicate, build lower hull popping while cross(h[k-2], h[k-1], p) <= 0 (pop right turns and collinear points), then build upper hull from right to left.

<details>

<summary>Show C++ Solution</summary>

#include <algorithm>
#include <iostream>
#include <vector>

struct Pt {
    long long x, y;
    bool operator<(const Pt& o) const { return x != o.x ? x < o.x : y < o.y; }
    bool operator==(const Pt& o) const { return x == o.x && y == o.y; }
};

long long cross(const Pt& O, const Pt& A, const Pt& B) {
    return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
}

std::vector<Pt> convexHull(std::vector<Pt> pts) {
    std::sort(pts.begin(), pts.end());
    pts.erase(std::unique(pts.begin(), pts.end()), pts.end());
    int n = static_cast<int>(pts.size());
    if (n <= 2) return pts;

    std::vector<Pt> h;
    for (const auto& p : pts) {
        while (h.size() >= 2 && cross(h[h.size() - 2], h.back(), p) <= 0) h.pop_back();
        h.push_back(p);
    }
    size_t lowerSz = h.size();
    for (int i = n - 2; i >= 0; --i) {
        while (h.size() > lowerSz && cross(h[h.size() - 2], h.back(), pts[i]) <= 0) h.pop_back();
        h.push_back(pts[i]);
    }
    h.pop_back();
    return h;
}

int main() {
    auto hull = convexHull({{0, 0}, {1, 1}, {2, 2}, {2, 0}, {0, 2}, {1, 0}});
    for (const auto& p : hull) std::cout << "(" << p.x << "," << p.y << ") ";
    std::cout << "\n"; // (0,0) (2,0) (2,2) (0,2)
    return 0;
}

</details>

---

Related Algorithms