Convex Hull — Graham Scan

The convex hull is the smallest convex set containing all input points, like a taut band around pins. Graham scan orders points by polar direction around a pivot, then maintains a stack of valid boundary turns. The implementation outputs only extreme vertices, excludes points in the interior of a straight hull edge, and uses exact bounded integer comparisons instead of approximate atan2 angles.

Prerequisites: Orientation; sorting comparators; stacks.

Build the idea

1. Choose and deduplicate

   Sort lexicographically and remove duplicate coordinates. Choose the lowest-y point, breaking ties by lowest x, as pivot. Every other point lies in the upper half-plane or on the rightward horizontal ray from it. This special position makes the sign of cross(pivot,A,B) a consistent polar-angle ordering; a general full-circle comparator would need an additional half-plane test.

2. Order equal rays by distance

   If two candidates have nonzero cross, the one producing a positive turn comes first. If cross is zero, sort by increasing squared distance from the pivot. A nearer collinear point will be removed when the farther point arrives. Exact tie rules give std::sort a strict ordering without epsilon comparisons or expensive trigonometry.

   $$\mathrm{keep}\mathrm{turn}\iff \mathrm{cross}(\mathrm{previous},\mathrm{last},\mathrm{next})>0$$

3. Maintain a convex stack

   Process the sorted points. While the last two stack vertices and the new point make a clockwise or flat turn, pop the last vertex. It cannot be an extreme point on the convex boundary of the processed angular prefix. Then append the candidate. Strict positive turns remain after every insertion, and angular order ensures no skipped point lies outside the final hull.

4. Trace the square and inner point

   For (0,0),(2,0),(2,2),(0,2),(1,1), the pivot is (0,0). Points on the diagonal ray are ordered (1,1) before (2,2); the flat-turn rule later removes (1,1). Output is the counterclockwise square starting at the pivot. A duplicate corner disappears during deduplication before any turn test.

5. Handle small and collinear sets

   No distinct points yields an empty hull; one yields that point. An all-collinear set reduces to its two extreme endpoints, or one if every input coincides. The output does not repeat its starting vertex. Each point is pushed once and popped at most once, explaining why the stack phase is linear despite its nested while loop.

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);
}
long long distance2(Point a,Point b){
    long long x=b.x-a.x,y=b.y-a.y;
    return x*x+y*y;
}
int main(){
    int n;
    std::cin>>n;
    std::vector<Point>p(n);
    for(auto&a:p){
        std::cin>>a.x>>a.y;
    }
    std::sort(p.begin(),p.end());
    p.erase(std::unique(p.begin(),p.end()),p.end());
    if(!p.empty()){
        auto pivot=std::min_element(p.begin(),p.end(),[](Point a,Point b){
            return a.y!=b.y?a.y<b.y:a.x<b.x;
        });
        std::iter_swap(p.begin(),pivot);
        Point base=p[0];
        std::sort(p.begin()+1,p.end(),[base](Point a,Point b){
            long long c=cross(base,a,b);
            return c!=0?c>0:distance2(base,a)<distance2(base,b);
        });
    }
    // Stack invariant: every remaining consecutive triple makes a strict left turn.
    std::vector<Point>hull;
    for(Point a:p){
        while(hull.size()>=2&&cross(hull[hull.size()-2],hull.back(),a)<=0){
            hull.pop_back();
        }
        hull.push_back(a);
    }
    std::cout<<hull.size()<<'\n';
    for(Point a:hull){
        std::cout<<a.x<<' '<<a.y<<'\n';
    }
}

Complexity analysis

O(n log n) time from sorting; deduplication and the amortized stack scan are O(n). O(n) point/hull storage, plus the sorting implementation’s logarithmic stack. Determinants and squared distances fit long long under the coordinate bound.

Example input and output

Read n (0..100000), then integer points within ±10^6. Print hull size and counterclockwise extreme vertices starting at lowest y, then lowest x. Boundary-collinear intermediate points are excluded.

Input

5
0 0
2 0
2 2
0 2
1 1

Output

4
0 0
2 0
2 2
0 2

The interior point lies on the pivot-to-corner ray but is not extreme and is removed.

Practical applications

Use to enclose an unordered point set, discard interior points before diameter calculations, and build convex geometry inputs. Andrew’s chain uses simpler lexicographic sorting and is often easier to implement; both have O(n log n) time.

Check your understanding

Why sort equal polar rays by increasing distance?

Put it into practice

Test duplicate corners, an all-collinear set and n=0,1,2.