Convex Hull
Build the outer envelope of a point set with monotone chain and use it as the basis for many geometry reductions.
Convex Hull
The main note is rendered from the TeX source. Code lives in a separate C++ file so the write-up stays readable.
Overview
The convex hull is the smallest convex polygon containing a set of points. In competitive programming it is often the first real geometry construction: once the hull is built, diameter, tangents, support lines, and several optimization problems become easier.
When to Use It
Use a convex hull when:
the answer depends only on the extreme points,
interior points are irrelevant noise,
you need a clean polygonal envelope before running rotating calipers or tangent queries.
Core Idea
The monotone-chain algorithm sorts the points, then builds the lower and upper hulls separately. While scanning, it removes the last point whenever the last two hull points together with the new point fail the chosen turn condition.
That means the hull is maintained as a sequence of valid turns instead of recomputed from scratch.
Key Insight
After sorting by \((x, y)\), every point is processed in the only order that matters for the lower and upper envelopes. If a point creates a non-left turn on the lower hull, it can never belong to the final lower envelope, so it is safe to remove immediately.
Operations / Main Technique
sort points lexicographically,
build the lower hull,
build the upper hull,
concatenate them while avoiding duplicate endpoints.
Worked example.
If three consecutive candidate points make a clockwise turn while building the lower hull, the middle point lies inside or on the boundary of the current envelope and can be removed.
Correctness Intuition
The hull must be convex, so each chain must keep turning in the same direction. Whenever three consecutive points break that rule, the middle one cannot be an extreme vertex of that chain. Repeating this local repair produces the global envelope.
Complexity Analysis
Sorting dominates the cost:
time: \(O(n \log n)\),
memory: \(O(n)\).
Implementation
The code uses monotone chain on integer points and returns the hull in counterclockwise order without repeating the first vertex at the end.
The only policy choice is how to treat collinear boundary points. The sample keeps the extreme endpoints and removes intermediate collinear points from each edge.
Common Pitfalls
Forgetting to remove duplicate input points first.
Using the wrong turn condition for the chosen collinearity policy.
Mishandling the cases \(n = 0\), \(1\), or \(2\).
Expecting interior collinear points to remain when the implementation intentionally compresses edges.
Variants / Extensions
Keep all boundary points by changing the pop condition.
Rotating calipers on the hull for diameter or width.
Dynamic hull maintenance, which is a different problem and much harder.
Practice Problems
Build the hull of a planar point set.
Compute the diameter of a point set after building the hull.
Count or list the vertices of the outer envelope only.
References
Code
Contest-ready reference implementation for the idea explained above.
struct Point {
long long x;
long long y;
bool operator<(const Point& other) const {
return x == other.x ? y < other.y : x < other.x;
}
bool operator==(const Point& other) const {
return x == other.x && y == other.y;
}
};
long long cross(Point a, Point b, Point c) {
long long x1 = b.x - a.x;
long long y1 = b.y - a.y;
long long x2 = c.x - a.x;
long long y2 = c.y - a.y;
return x1 * y2 - y1 * x2;
}
vector<Point> convex_hull(vector<Point> pts) {
sort(pts.begin(), pts.end());
pts.erase(unique(pts.begin(), pts.end()), pts.end());
if ((int)pts.size() <= 1) {
return pts;
}
vector<Point> lower, upper;
for (Point p : pts) {
while ((int)lower.size() >= 2 && cross(lower[(int)lower.size() - 2], lower.back(), p) <= 0) {
lower.pop_back();
}
lower.push_back(p);
}
for (int i = (int)pts.size() - 1; i >= 0; --i) {
Point p = pts[i];
while ((int)upper.size() >= 2 && cross(upper[(int)upper.size() - 2], upper.back(), p) <= 0) {
upper.pop_back();
}
upper.push_back(p);
}
lower.pop_back();
upper.pop_back();
lower.insert(lower.end(), upper.begin(), upper.end());
return lower;
}
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.