Convex Hull — Andrew's Monotone Chain

Andrew’s monotone chain constructs the same extreme-vertex convex hull as Graham scan using only lexicographic sorting. It builds a lower boundary from left to right and an upper boundary in reverse. This is a reliable competition default because the comparator is simple and all geometry decisions occur in the same orientation predicate. Duplicates, small sets and collinearity have explicit output rules.

Prerequisites: Graham Scan; Orientation; amortized stack analysis.

Build the idea

1. Sort and remove duplicates

   Order points by x, then y. Equal coordinates become adjacent and std::unique removes them. The leftmost and rightmost remaining points anchor both chains. Returning immediately for zero or one point avoids assumptions that two endpoints exist. A hull is a geometric set, so repeated input points do not create repeated hull vertices.

2. Construct the lower chain

   Scan sorted points. While the last two stored vertices and the next point form a non-left turn, remove the last stored vertex. The discarded point lies on or above a segment that belongs to the lower convex envelope, so retaining it would introduce a flat or inward bend. Append the new point after the turn becomes strictly positive.

   $$\mathrm{lower}+\mathrm{upper}=\mathrm{counterclockwise}\mathrm{hull}$$

3. Construct the upper chain

   Apply the same left-turn loop while scanning the points in reverse lexicographic order. Reversal lets one identical predicate build the opposite side. Each chain contains both extreme endpoints; remove its final endpoint before concatenating, so the combined cycle contains each corner once and does not repeat the starting point.

4. Work a boundary-collinear example

   For points (0,0),(1,0),(2,0),(2,2),(0,2),(1,1), the lower scan removes (1,0) because it is flat, while later turns remove interior candidates such as (1,1). The upper scan supplies the top boundary. Output starts at (0,0) and walks counterclockwise through (2,0),(2,2),(0,2).

5. Prove the cost and compare

   Every candidate enters each chain once and can leave it at most once, so both scans together are O(n). Sorting dominates. Graham scan first orders angles around a pivot; Andrew orders coordinates and builds two envelopes. Both use the same turn invariant and exclude intermediate collinear boundary points in the shown versions. An all-collinear set returns just the two endpoints.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<vector>
#include<algorithm>
struct Point{
    long long x,y;
    bool operator<(Point b)const{
        return x!=b.x?x<b.x:y<b.y;
    }
    bool operator==(Point b)const{
        return x==b.x&&y==b.y;
    }
};
long long cross(Point a,Point b,Point c){
    return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
std::vector<Point>hull(std::vector<Point>p){
    std::sort(p.begin(),p.end());
    p.erase(std::unique(p.begin(),p.end()),p.end());
    if(p.size()<=1){
        return p;
    }
    // Each candidate is pushed and popped at most once on each chain.
    std::vector<Point>lower,upper;
    for(Point a:p){
        while(lower.size()>=2&&cross(lower[lower.size()-2],lower.back(),a)<=0){
            lower.pop_back();
        }
        lower.push_back(a);
    }
    for(auto it=p.rbegin();it!=p.rend();++it){
        Point a=*it;
        while(upper.size()>=2&&cross(upper[upper.size()-2],upper.back(),a)<=0){
            upper.pop_back();
        }
        upper.push_back(a);
    }
    lower.pop_back();
    upper.pop_back();
    lower.insert(lower.end(),upper.begin(),upper.end());
    return lower;
}
int main(){
    int n;
    std::cin>>n;
    std::vector<Point>p(n);
    for(auto&a:p){
        std::cin>>a.x>>a.y;
    }
    p=hull(p);
    std::cout<<p.size()<<'\n';
    for(Point a:p){
        std::cout<<a.x<<' '<<a.y<<'\n';
    }
}

Complexity analysis

O(n log n) time for sorting and O(n) for both amortized scans. O(n) storage for points and the two chains. All predicates are exact under the stated ±10^6 coordinate bound.

Example input and output

Read n (0..100000), then integer points within ±10^6. Print hull size and counterclockwise extreme vertices, beginning at lexicographically smallest. Exclude redundant collinear points and the repeated closing vertex.

Input

6
0 0
1 0
2 0
2 2
0 2
1 1

Output

4
0 0
2 0
2 2
0 2

The bottom-edge middle point and the interior point are not extreme hull vertices.

Practical applications

Use as a reusable hull primitive for area, diameter, support directions and collision geometry. Graham scan is equally asymptotic but needs a careful polar comparator. For already sorted input the construction scans are linear.

Check your understanding

Why does the nested popping loop remain linear after sorting?

Put it into practice

Compare the vertex sets from both hull lessons on random inputs.