Convex Hull: Algorithm, Mathematics, Complexity, and Applications

1. Algorithm Overview

The convex hull of a set of points in the plane is the smallest convex polygon that contains all the points. A standard way to compute it in O(n log n) time is Andrew’s Monotone Chain (a variant of Graham’s scan):

1. Sort points by x (then y) coordinate.
2. Build the lower hull: vector<Point> lower; For each point p in sorted order:
   • While lower.size() ≥ 2 and the last two points a, b in lower together with p make a non‐left turn (cross ≤ 0), pop back.
   • Push p onto lower.
3. Build the upper hull similarly by scanning in reverse order.
4. Concatenate lower and upper (dropping duplicate endpoints) ⇒ the convex hull in counterclockwise order.

Time Complexity

• Sorting: O(n log n).
• Building hull: each point pushed/popped at most once ⇒ O(n).

Total: O(n log n).

Memory Complexity

Storing input points and the hull (each ≤ n points): O(n).

---

2. Mathematics of Convex Hulls

• Convexity: A polygon is convex if every line segment between two points in it lies entirely inside it.
• Cross Product Test: For three points A(x₁,y₁), B(x₂,y₂), C(x₃,y₃), the signed area is

  cross = (x₂–x₁)*(y₃–y₁) – (y₂–y₁)*(x₃–x₁)

  • cross > 0 ⇒ ABC makes a left turn (counter‐clockwise) • cross < 0 ⇒ right turn • cross = 0 ⇒ collinear.
• Why Monotone Chain Works: Sorting ensures we sweep from leftmost to rightmost; the cross‐product test maintains convexity by discarding “inward” corners.

---

3. Easy Problems

3.1 – Codeforces 70D “Point on Convex Hull?”

You are given a convex polygon (its vertices in order) and Q query points. For each query, answer “YES” if the point lies inside or on the polygon, else “NO.”

#include <iostream>
#include <vector>
using namespace std;

struct P { long long x, y; };

long long cross(const P &a, const P &b, const P &c) {
    return (b.x - a.x)*(c.y - a.y) - (b.y - a.y)*(c.x - a.x);
}

// check if point q is inside convex polygon poly (ccw order)
bool inConvex(const vector<P> &poly, const P &q) {
    int n = poly.size();
    if (cross(poly[0], poly[1], q) < 0) return false;
    if (cross(poly[0], poly[n-1], q) > 0) return false;
    // binary search to find wedge
    int l = 1, r = n-1;
    while (r - l > 1) {
        int m = (l + r)/2;
        if (cross(poly[0], poly[m], q) >= 0) l = m;
        else r = m;
    }
    return cross(poly[l], poly[l+1], q) >= 0;
}

int main(){
    int n; cin >> n;
    vector<P> poly(n);
    for(int i=0;i<n;i++) cin>>poly[i].x>>poly[i].y;
    int Q; cin>>Q;
    while(Q--){
        P q; cin>>q.x>>q.y;
        cout<<(inConvex(poly,q)?"YES":"NO")<<"\n";
    }
    return 0;
}

3.2 – Codeforces 22B “Farthest Pair”

Given N points, find the maximum squared distance between any two. Compute the convex hull, then apply rotating calipers in O(n).

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;

struct P { ll x, y; };

ll cross(const P &a, const P &b, const P &c) {
    return (b.x-a.x)*(c.y-a.y) - (b.y-a.y)*(c.x-a.x);
}

ll dist2(const P &a, const P &b){
    ll dx = a.x-b.x, dy = a.y-b.y;
    return dx*dx + dy*dy;
}

vector<P> convexHull(vector<P>& pts){
    sort(pts.begin(), pts.end(), [](auto &a, auto &b){
        return a.x<b.x || (a.x==b.x && a.y<b.y);
    });
    int n=pts.size(), k=0;
    vector<P> h(2*n);
    // lower
    for(int i=0;i<n;i++){
        while(k>=2 && cross(h[k-2],h[k-1],pts[i])<=0) k--;
        h[k++]=pts[i];
    }
    // upper
    for(int i=n-2,t=k+1;i>=0;i--){
        while(k>=t && cross(h[k-2],h[k-1],pts[i])<=0) k--;
        h[k++]=pts[i];
    }
    h.resize(k-1);
    return h;
}

int main(){
    int N; cin>>N;
    vector<P> pts(N);
    for(int i=0;i<N;i++) cin>>pts[i].x>>pts[i].y;
    auto h = convexHull(pts);
    int m = h.size();
    if(m==1){ cout<<0<<"\n"; return 0; }
    ll best = 0;
    int j = 1;
    for(int i=0;i<m;i++){
        while(abs(cross(h[i], h[(i+1)%m], h[(j+1)%m])) >
              abs(cross(h[i], h[(i+1)%m], h[j]))) {
            j = (j+1)%m;
        }
        best = max({best, dist2(h[i],h[j]), dist2(h[(i+1)%m],h[j])});
    }
    cout<<best<<"\n";
    return 0;
}

---

4. Intermediate Problems

4.1 – Codeforces 137B “Fence Painting”

You have N fence posts on a line; each has a height. You want to pick a subset that forms a convex “chain” (no dips). Model each post as point (i, h_i) and compute longest convex subsequence via DP with cross‐product checks.

#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
struct P{ ll x,y; };

ll cross(const P &a,const P &b,const P &c){
    return (b.x-a.x)*(c.y-a.y) - (b.y-a.y)*(c.x-a.x);
}

int main(){
    int n; cin>>n;
    vector<P> pts(n);
    for(int i=0;i<n;i++){
        pts[i]={i,0};
        cin>>pts[i].y;
    }
    vector<int> dp(n,1);
    int ans=1;
    for(int i=0;i<n;i++){
        for(int j=0;j<i;j++){
            if(j<1 || cross(pts[j-1],pts[j],pts[i])>0){
                dp[i]=max(dp[i], dp[j]+1);
            }
        }
        ans=max(ans, dp[i]);
    }
    cout<<ans<<"\n";
    return 0;
}

4.2 – Codeforces 70D “Dynamic Convex Hull Queries”

Maintain a dynamic set of points under insertions, and after each insertion answer the area of the convex hull. Use two monotone chains and a balanced BST or deque.

#include <iostream>
#include <set>
#include <cmath>
using namespace std;
using ll = long long;

struct P{ ll x,y; };

ll cross(const P &a,const P &b,const P &c){
    return (b.x-a.x)*(c.y-a.y) - (b.y-a.y)*(c.x-a.x);
}

// Simplified: rebuild hull on each query for clarity
double hullArea(const vector<P>& h){
    int m = h.size();
    if(m<3) return 0.0;
    ll area2 = 0;
    for(int i=0;i<m;i++){
        int j=(i+1)%m;
        area2 += h[i].x*h[j].y - h[j].x*h[i].y;
    }
    return fabs(area2)/2.0;
}

vector<P> computeHull(vector<P>& pts){
    sort(pts.begin(), pts.end(), [](auto &a, auto &b){
        return a.x<b.x || (a.x==b.x && a.y<b.y);
    });
    int n=pts.size(), k=0;
    vector<P> h(2*n);
    for(int i=0;i<n;i++){
        while(k>=2 && cross(h[k-2],h[k-1],pts[i])<=0) k--;
        h[k++]=pts[i];
    }
    for(int i=n-2,t=k+1;i>=0;i--){
        while(k>=t && cross(h[k-2],h[k-1],pts[i])<=0) k--;
        h[k++]=pts[i];
    }
    h.resize(k-1);
    return h;
}

int main(){
    int Q; cin>>Q;
    vector<P> pts;
    while(Q--){
        P p; cin>>p.x>>p.y;
        pts.push_back(p);
        auto h = computeHull(pts);
        cout<<hullArea(h)<<"\n";
    }
    return 0;
}

---

5. Hard Problem

5.1 – Codeforces 1093G “Convex Floor”

Given a convex polygon of N vertices and M query points, for each query find the nearest point on the polygon. Project each query point onto each edge (in O(1)) and take the minimum distance, or use binary‐search by angle for O(log N) per query.

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

struct P{ double x,y; };

double dist2(const P &a,const P &b){
    double dx=a.x-b.x, dy=a.y-b.y;
    return dx*dx+dy*dy;
}

// project q onto segment [a,b]
P project(const P &a,const P &b,const P &q){
    double vx=b.x-a.x, vy=b.y-a.y;
    double t = ((q.x-a.x)*vx + (q.y-a.y)*vy)/(vx*vx+vy*vy);
    t = max(0.0, min(1.0, t));
    return {a.x + t*vx, a.y + t*vy};
}

int main(){
    int N,M; cin>>N>>M;
    vector<P> hull(N);
    for(int i=0;i<N;i++) cin>>hull[i].x>>hull[i].y;
    while(M--){
        P q; cin>>q.x>>q.y;
        double best = 1e300; P ans{0,0};
        for(int i=0;i<N;i++){
            P p = project(hull[i], hull[(i+1)%N], q);
            double d = dist2(p,q);
            if(d<best){ best=d; ans=p; }
        }
        cout<<"("<<ans.x<<","<<ans.y<<")\n";
    }
    return 0;
}