Convex hull with the monotone chain

Why this matters when you build with AI

Ask an AI tool for a convex hull and it often returns a Graham scan: pick the lowest point, sort the others by angle with atan2, and run a stack. That version works on random points and breaks on the inputs contest data is built from. Two points on the same ray from the lowest point get sorted in an unclear order, the stack keeps a point that is not on the hull, and a single point produces a hull with no edges. The tool then says the code is "robust" and gives no test for those cases.

A second common problem is that the tool drops collinear points without being asked. A problem that asks for "the number of input points on the fence" needs those points, and the tool's answer is wrong by exactly the number of points on each edge. You catch both problems with three short tests: one point, all points on one line, and a square with a point in the middle of one side. This lesson gives a method that avoids angles completely, shows the real output of each test, and checks the code against a brute force on 3000 random inputs.

Terms used here

A point is a pair of integers (x, y). The cross product cross(o, a, b) is (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x). It is positive when b lies to the left of the line from o to a, negative when it lies to the right, and zero when the three points are on one line. Lesson 01 explains where this comes from.

A convex polygon is a polygon with no inward dent: every segment between two of its points stays inside it. The convex hull of a set of points is the smallest convex polygon that contains all of them. Think of stretching a rubber band around nails placed at the points.

The corners of a hull are the points where the boundary turns. The boundary points are all input points that lie on the hull, corners and points in the middle of an edge. A problem may ask for either set, so the code must be able to return both. Counterclockwise (CCW) order means walking the boundary so that the inside is on your left.

Duplicate points are two or more input points with the same coordinates. Degenerate input means input where the hull has no area: one point, two points, or many points on one line.

The idea: two chains from left to right

Sort the points by x, and break ties by y. The leftmost point is the first in the list and the rightmost is the last. The hull is made of two chains between these two points. The lower chain runs along the bottom, and the upper chain runs back along the top.

Build the lower chain with a stack. Go through the sorted points in order. Before pushing a new point p, look at the last two points on the stack, a and b, where b is the top. If cross(a, b, p) is negative, then the turn a to b to p goes clockwise, which is a right turn. A lower chain only turns left, so b is inside the hull and must be removed. Pop b and check again. When the turn is positive, push p.

Build the upper chain the same way, but go through the points from right to left. A turn that goes clockwise is again the one to remove.

Take the five points (0,0), (2,0), (1,1), (2,2) and (0,2). After sorting, the order is (0,0), (0,2), (1,1), (2,0), (2,2).

The lower chain starts with (0,0) and (0,2) on the stack. The next point is (1,1). Here cross((0,0), (0,2), (1,1)) is 0 * 1 - 2 * 1 = -2, which is negative, so (0,2) is popped. The stack is (0,0), (1,1). The next point is (2,0), and cross((0,0), (1,1), (2,0)) is 1 * 0 - 1 * 2 = -2, so (1,1) is popped. The stack is (0,0), (2,0). The point (2,2) gives cross((0,0), (2,0), (2,2)) equal to 2 * 2 - 0 * 2 = 4, which is positive, so it is pushed. The lower chain is (0,0), (2,0), (2,2).

The upper chain starts from (2,0) and goes back to (0,0). It pops (2,0) when (1,1) arrives and pushes (1,1), then pops (1,1) when (0,2) arrives, and finally pushes (0,0). The result is the four corners (0,0), (2,0), (2,2), (0,2) in CCW order. The point (1,1) is in the middle of the square and was removed. Running the program on this input gives:

The first line is twice the area of the hull, which is 2 * 2 * 2 = 8 for a square of side 2. The second line is the perimeter, 8.000000. The third line is the number of corners, 4. The fourth line is the number of distinct input points on the boundary, also 4, because (1,1) is inside.

Why this is O(n log n)

Sorting takes O(n log n) time. After that, each point is pushed once per chain and popped at most once, so the chain loops take O(n) in total, even though a single point can cause many pops. The sort is the only step that costs more than linear time.

Keep or drop collinear boundary points

A straight turn has cross product zero. Points (0,0), (1,0) and (2,0) on one line make a straight turn at (1,0). The stack rule decides what happens to it. If the rule pops straight turns, the middle point is removed and the chain has only the endpoints. If the rule keeps straight turns, the middle point stays.

The code uses one flag, keep_collinear, that changes only the pop test. Without the flag, a turn with cross less than or equal to zero is popped. With the flag, only a cross less than zero is popped. The flag also controls the degenerate branch described below.

For the input (0,0), (1,0), (2,0), the real program gives this output:

The corners are 2: (0,0) and (2,0). The boundary has 3 points, because (1,0) is on the fence. The perimeter is 2 * 2 = 4, which is the length of the segment walked there and back. The area is 0.

Duplicates and degenerate input

The code sorts the points and removes duplicates with unique. After that, one point is returned directly, and two or more distinct points go on to the next check.

A set of points is all on one line when every point has cross zero with the first and last sorted points. Chains do not work for that case: with keep mode, both chains walk along the same line and the middle points appear twice. I ran the same code without that check on the input (0,0), (1,0), (2,0) and it printed a boundary count of 4 where the right answer is 3. The branch returns the two ends in drop mode, and all distinct points in sorted order in keep mode.

Overflow limits

Coordinates are at most 10^9 in absolute value, so each difference is at most 2 * 10^9. A product of two differences is at most 4 * 10^18, and the cross product is a difference of two such products, so it is at most 8 * 10^18 in absolute value. A signed 64-bit integer holds up to about 9.22 * 10^18, so the cross product fits.

The doubled area can also be as large as 8 * 10^18, for the square with corners at (-10^9, -10^9) and (10^9, 10^9). The code adds the fan triangles from h[0]. Each triangle has a non-negative doubled area, so the running sum never falls, and it never goes above the final answer. The sum therefore stays inside the same range.

The corner lengths are computed in long double. The squared length of one edge is up to 8 * 10^18, which long double holds exactly on the usual x86 platforms, but the square root is approximate, so the perimeter is printed with six decimals.

Worked example: the fence problem

The problem below is original and asks for three things with one flag used twice.

Input: a first line N, then N lines x y. N is at most 200000, and every coordinate is between -10^9 and 10^9.

Output: four lines. Line 1 is twice the area of the convex hull. Line 2 is the perimeter with six decimals. Line 3 is the number of corners. Line 4 is the number of distinct input points on the boundary.

For the first sample, the output is the one from the walkthrough above. For the second sample, (0,0), (3,3), (1,1), (3,3), the distinct points are on the line from (0,0) to (3,3). The output is 0, 8.485281, 2, 3. The perimeter is 2 * sqrt(18), which is 8.485281 after rounding. The third sample has one point repeated twice, and the output is 0, 0.000000, 1, 1.

The full program, tested as shown in the next section, is below.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
struct Pt {
    ll x, y;
};
 
bool operator<(const Pt& a, const Pt& b) {
    return a.x < b.x || (a.x == b.x && a.y < b.y);
}
 
bool operator==(const Pt& a, const Pt& b) {
    return a.x == b.x && a.y == b.y;
}
 
// Twice the signed area of the triangle o, a, b.
// Positive when b is to the left of the directed line o -> a.
ll 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);
}
 
// Convex hull in counterclockwise order, starting at the lowest-leftmost point.
// keep_collinear == false: only the corner points are returned.
// keep_collinear == true: every distinct input point on the boundary is returned.
// If all points are on one line, the hull is that segment: the two ends
// (drop mode) or all distinct points from one end to the other (keep mode).
vector<Pt> convex_hull(vector<Pt> p, bool keep_collinear) {
    sort(p.begin(), p.end());
    p.erase(unique(p.begin(), p.end()), p.end());
    int n = p.size();
    if (n <= 1) return p;
 
    bool all_collinear = true;
    for (int i = 1; i + 1 < n && all_collinear; i++)
        if (cross(p[0], p[n - 1], p[i]) != 0) all_collinear = false;
    if (all_collinear) return keep_collinear ? p : vector<Pt>{p[0], p[n - 1]};
 
    vector<Pt> h(2 * n);
    int k = 0;
    // A turn that is clockwise (cross < 0) always goes. A straight turn
    // (cross == 0) goes only in drop mode.
    auto must_pop = [&](ll c) { return keep_collinear ? c < 0 : c <= 0; };
 
    // Lower chain: left to right.
    for (int i = 0; i < n; i++) {
        while (k >= 2 && must_pop(cross(h[k - 2], h[k - 1], p[i]))) k--;
        h[k++] = p[i];
    }
    // Upper chain: right to left. The chain may not pop below its own start.
    for (int i = n - 2, lower = k + 1; i >= 0; i--) {
        while (k >= lower && must_pop(cross(h[k - 2], h[k - 1], p[i]))) k--;
        h[k++] = p[i];
    }
    h.resize(k - 1);  // the last point pushed equals the first point
    return h;
}
 
// Twice the area of a counterclockwise polygon, fanned from h[0].
// Every fan triangle has area >= 0 for a convex polygon, so the running sum
// only grows and never goes above the final doubled area.
ll doubled_area(const vector<Pt>& h) {
    ll s = 0;
    for (size_t i = 1; i + 1 < h.size(); i++) s += cross(h[0], h[i], h[i + 1]);
    return s;
}
 
int main() {
    int n;
    if (scanf("%d", &n) != 1) return 0;
    vector<Pt> p(n);
    for (auto& q : p)
        if (scanf("%lld %lld", &q.x, &q.y) != 2) return 1;
 
    vector<Pt> corners = convex_hull(p, false);
    vector<Pt> boundary = convex_hull(p, true);
 
    long double len = 0;
    int m = corners.size();
    for (int i = 0; i < m; i++) {
        const Pt& a = corners[i];
        const Pt& b = corners[(i + 1) % m];
        ll dx = a.x - b.x, dy = a.y - b.y;
        len += sqrtl((long double)dx * dx + (long double)dy * dy);
    }
    printf("%lld\n%.6Lf\n%d\n%d\n", doubled_area(corners), len, m, (int)boundary.size());
    return 0;
}

Compile and run it like this:

g++ -std=c++17 -O2 -Wall -Wextra -o hull hull.cpp
./hull < sample.txt

How it was tested

I compiled the program with g++ -std=c++17 -O2 -Wall -Wextra using g++ 15.2.0 on Linux, and I ran it on the inputs shown above. All the outputs in this lesson are copied from those runs.

To test the program, I wrote a Python brute force that does not use the chain. It takes the distinct points, and for every pair of points it checks whether all the others lie on one side of the line through the pair. If so, that line is a supporting line, and every point on it is a boundary point. The corners are the boundary points that are not strictly between two other input points. The brute force then orders the corners by angle around their average and computes the area and perimeter from that order. It is O(n^3) or worse, so it is only used for small inputs.

I ran 3000 random cases, with between 1 and 9 points, coordinates in small ranges from -2 to 20, and about a third of the cases forced onto one line. All 3000 matched the brute force on the doubled area, the perimeter within 1e-6, the corner count and the boundary count. The test counted the cases it covered: 1037 all-collinear, 943 with duplicate points, 1025 where the boundary count was larger than the corner count, and 347 with a single distinct point.

For speed, I generated 200000 random points with coordinates up to 10^9 and ran the program on them. It took about 0.07 seconds of wall time on my machine, and it printed a doubled area of 7999160085694265734 with 28 corners. Your timing will differ by machine.

The monotone chain method is from A. M. Andrew, "Another efficient algorithm for convex hulls in two dimensions", Information Processing Letters, volume 9, issue 5, 1979, pages 216 to 219. I checked the bibliographic record in DBLP. I did not read the paper itself, so the description above is my own, and the claims it rests on are the ones I tested.

Common mistakes

Floating-point angles. A Graham scan sorts by atan2. Two points on the same ray from the start point can come out in either order, and the stack then keeps a point that is not on the hull. The fix is the cross product test in this lesson, which uses only integers.

Dropping the all-collinear branch. Without the branch, the input (0,0), (1,0), (2,0) gives a boundary count of 4. The correct count is 3. The symptom appears only in keep mode, so a test that only checks corners passes.

Forgetting duplicates. Two copies of the same point can give a zero-length edge and a repeated corner, so the corner count and the boundary count can come out too high. The code removes duplicates before the chain runs for this reason.

32-bit integers. The program with int in place of long long printed -991952896 for the square with corners at (-10^9, -10^9) and (10^9, 10^9). The right answer is 8000000000000000000. The product of two differences overflows 32 bits in the first step. Small inputs fit in 32 bits, so a test on small points would not show the bug.

Printing the wrong quantity. The doubled area is an integer and the area is half of it. A problem that asks for "area" may expect a fraction. Print the doubled value only when the problem says so.

Testing on random points only. Random points with coordinates up to 10^9 are almost never collinear, so they rarely reach the degenerate branch. Test on small coordinates, where collinear and duplicate points are common.

Prompt for checking AI-written hull code

Use this prompt to test code an AI tool wrote for you, and read the answer against the points under "What a good answer looks like".

Here is my convex hull function in C++17. It takes a vector of integer points with coordinates up to 1e9 in absolute value. Check it for these cases: one point, two equal points, three points on one line, a square with a point in the middle of one side, and 200000 random points. Do not use floating point. Show the input you used for each case and the exact output, and say which outputs you did not run.

A good answer uses integer cross products only, has one branch for points that are all on one line, removes duplicates before the chain, and shows the output of each case it ran. It also says which cases it did not run. Check the answer by running the three degenerate cases yourself. The square with a midpoint on one side should give 8 / 8.000000 / 4 / 5 in the fence program above, and the answer should say so.

Checklist

Sort by x, then y, and remove duplicates before anything else.
Return one point directly, and handle all-collinear input with a separate branch.
Use only integer cross products for every turn test.
Pop on a clockwise turn always, and on a straight turn only when corners are wanted.
Compute the doubled area as an integer with fan triangles from h[0].
Test a square with a point on one side, a repeated point, and a line of points against a brute force.

Summary

The monotone chain builds the lower and upper chains from sorted points with a stack and a cross product test. The sort costs O(n log n), and the rest is linear. One flag decides whether straight turns are popped, which gives corners only or all boundary points. Duplicates and all-collinear input need their own handling, because the chain alone gives wrong counts in keep mode. With coordinates up to 10^9, the cross products and the doubled area fit in signed 64-bit integers, and the 32-bit version is wrong on the largest squares.

Practice problems

Each practice input can be checked with the fence program. Try the problem first, then open the answer.

Square with a midpoint. The input is 5 points: (0,0), (4,0), (4,4), (0,4) and (2,0). Find the four output lines.

Show the answer
```
32
16.000000
4
5
```
The square has side 4, so its area is 16 and its doubled area is 32. Its perimeter is 16. The point (2,0) is on the bottom edge, so it counts as a boundary point but not as a corner.
One point. The input is 1 point: (7,-3). Find the four output lines.

Show the answer
```
0
0.000000
1
1
```
One point has no edges, so the perimeter is zero. It is the only corner and the only boundary point.
Segment. The input is 2 points: (0,0) and (3,4). Find the four output lines.

Show the answer
```
0
10.000000
2
2
```
The segment has length 5. The perimeter counts the walk from one end to the other and back, so it is 10. Both points are corners and both are boundary points.
Triangle with a point on an edge. The input is 4 points: (0,0), (2,0), (1,0) and (1,1). Find the four output lines.

Show the answer
```
2
4.828427
3
4
```
The triangle has base 2 and height 1, so its doubled area is 2. Its sides are 2, sqrt(2) and sqrt(2), which sum to about 4.828427. The point (1,0) lies on the base, so it is a boundary point and not a corner.
Why keep mode needs its own branch. Explain, in your own words, why the all-collinear branch is needed in keep mode and what the chain returns without it for the input (0,0), (1,0), (2,0).

Show the answer

On a line, the lower chain keeps the middle point and the upper chain keeps it again, so it appears twice in the list. Without the branch, the program printed a boundary count of 4 for this input. The correct count is 3, one for each distinct point. The branch returns the distinct points directly, once each, so the count is right.