Convex hull
The convex hull of a set of points is the smallest convex polygon that contains all of them. The monotone chain algorithm finds its corners in order in O(n \log n) time, using only the sign of a cross product. For the dynamic programming technique with a similar name, see the convex hull trick.
Explanation
Eight nails stand in a board, numbered from left to right. Stretch a rubber band around all of them and let go. It catches on nails 1, 5, 7, 8, 6 and 3; nails 2 and 4 are inside. The shape of the band is the convex hull of the points.
Fig. 1. The band around the eight points, and a red path from 1 through 2 to 5.
Go around the band counterclockwise, from point 1 to 5, 7, 8, 6, 3 and back to 1. At every point you turn left. At point 5, for example, the step in is 6 right and 4 down, the step out is 2 right and 1 up, and the cross product 6 · 1 − (−4) · 2 = 14 is positive. If the band went from 1 to 5 through point 2, along the red path, it would turn right at 2. So if a path through a point turns right there, the band does not touch that point.
The program gets a list of points and must find which ones the band touches, in order around it, using only the turn test on three points. A direct way is to test every pair of points: the band has a side from one point to another if all other points lie to its left. For 10^5 points that is about 10^{15} checks. Almost all of that work tests pairs that are not neighbours on the band. If we knew the order in which the band meets the points, we would only have to check each point against its neighbours.
Nothing lies to the left of the leftmost point, so the band must touch it, and the same holds for the rightmost point. These two points cut the hull into the lower hull below and the upper hull above. Going along the lower hull from left to right is going counterclockwise around the band, so it turns left at every point, and x only grows along it. So sort the points from left to right and walk through them in that order. Keep the points that so far look like the lower hull on a stack: a point joins it with a push and leaves it with a pop, and the stack must turn left at every point.
The first thing to try is one check per new point. When a point arrives, look at the top two points of the stack and the new one. If they turn right, pop the top one, then push the new point. The stack starts as 1, 2, 3. Point 4 comes: 2, 3, 4 turn right, so 3 is popped and the stack is 1, 2, 4. Point 5 comes: 2, 4, 5 turn right, so 4 is popped and the stack is 1, 2, 5. Then point 6 is pushed, point 7 pops 6, and point 8 is pushed. The stack ends as 1, 2, 5, 7, 8, and point 2 is still on it.
Fig. 2. Red: the stack after one check per point. Blue: the lower hull.
Point 2 lies above the straight line from 1 to 5, and the red line turns right at 2, just as the red path in Fig. 1 does.
Popping point 4 made points 2 and 5 neighbours, and 1, 2, 5 can turn right just as 2, 4, 5 did. So check again, and keep popping while the top two points and the new one turn right. At point 5 this pops 4 and then 2, and the lower hull becomes 1, 5, 7, 8, the blue line. Treat three points on one line like a right turn and pop the middle one: a point in the middle of a straight side is not a corner. The same walk from right to left gives the upper hull.
Each point is pushed once per walk and popped at most once, so a walk takes at most about steps. The sort costs more, O(n \log n), and that is the time of the whole algorithm; the memory is .
This is the monotone chain algorithm, also called Andrew's algorithm. It sorts the points, builds the lower hull from left to right and the upper hull from right to left, and pops while the last turn is not left.
Lower walk: push 1. The highlighted point is the new one; the row below is the stack, bottom on the left.
Fig. 3. Step through the monotone chain with the buttons or the arrow keys. The stack is below the points, bottom on the left.
Point 3 was popped in the lower walk but came back in the upper one.
Implementation
The points are kept in a vector p, with Point, vec, cross and orient from geometry basics. After the sort, repeated points are neighbours. unique keeps one copy of each run of equal neighbours at the front and returns where the kept part ends; erase cuts off the rest.
The loop needs the top of the stack, h.back(), and the point under it, h[h.size() - 2]. std::stack can't give the second one, so h is a vector with push_back and pop_back. After the lower walk, lower is the size of h, and the upper walk pops only while h.size() > lower, so it never removes the lower hull.
Sort: by
x, then byy; remove repeated points.Lower walk: for each point from left to right, pop while the top two points on the stack and the new point don't turn left, then push the new point.
Upper walk: the same from right to left, never popping below the lower hull.
Join: the last point pushed is the first point again; remove it.
The input is n (1 \le n \le 10^5), then n lines x y with integers |x|, |y| \le 10^9, in any order, repeats allowed. The program prints the number of corners, then the corners counterclockwise, starting from the leftmost point (the lowest one if there are several). Then it prints the perimeter and the area of the hull. For the 8 points above the input is:
8
6 0
2 3
9 4
3 7
0 4
8 1
4 3
7 6#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <vector>
using namespace std;
struct Point { long long x, y; };
Point vec(Point a, Point b) { return {b.x - a.x, b.y - a.y}; }
long long cross(Point u, Point v) { return u.x * v.y - u.y * v.x; }
// 1: a -> b -> c turns left, -1: turns right, 0: a, b, c on one line
int orient(Point a, Point b, Point c) {
long long s = cross(vec(a, b), vec(a, c));
if (s > 0) return 1;
if (s < 0) return -1;
return 0;
}
int main() {
int n;
cin >> n;
vector<Point> p(n);
for (auto& q : p) cin >> q.x >> q.y;
// sort: by x, then by y; remove repeated points
sort(p.begin(), p.end(), [](Point a, Point b) {
return a.x < b.x || (a.x == b.x && a.y < b.y);
});
p.erase(unique(p.begin(), p.end(), [](Point a, Point b) {
return a.x == b.x && a.y == b.y;
}), p.end());
n = p.size();
vector<Point> h; // the stack
// lower walk: left to right
for (int i = 0; i < n; i++) {
// change <= 0 to < 0 to keep points in the middle of a side
while (h.size() >= 2 && orient(h[h.size() - 2], h.back(), p[i]) <= 0)
h.pop_back(); // pop
h.push_back(p[i]); // push
}
// upper walk: right to left
int lower = h.size();
for (int i = n - 2; i >= 0; i--) {
// change <= 0 to < 0 to keep points in the middle of a side
while ((int)h.size() > lower && orient(h[h.size() - 2], h.back(), p[i]) <= 0)
h.pop_back(); // pop
h.push_back(p[i]); // push
}
// join: the last point pushed is p[0] again (with one point there is no upper walk)
if (n > 1) h.pop_back();
cout << h.size() << "\n";
for (Point q : h) cout << q.x << " " << q.y << "\n";
// perimeter and area; remove this block if you only need the corners
int k = h.size();
double perimeter = 0;
for (int i = 0; i < k; i++) {
Point d = vec(h[i], h[(i + 1) % k]);
perimeter += sqrt((double)d.x * d.x + (double)d.y * d.y);
}
long long s = 0; // twice the area
for (int i = 1; i + 1 < k; i++)
s += cross(vec(h[0], h[i]), vec(h[0], h[i + 1]));
cout << fixed << setprecision(3) << perimeter << "\n";
cout << s / 2 << (s % 2 ? ".5" : ".0") << "\n";
}If all points lie on one line, the program prints the two end points. A problem that forbids three corners on one line needs <= 0; a problem that asks for every point on the boundary needs < 0. With < 0, points that all lie on one line come out with the middle points twice, once from each walk, so such problems usually promise that the points are not all on one line.
Perimeter and area
The shortest fence around the points runs along the hull. Its length adds the side lengths, including the side from the last corner back to the first. The area inside is the polygon area of the corners, cut into triangles from corner h[0]; the corners go counterclockwise, so s is twice the area and never negative. For a hull of two points the fence goes there and back, so its length is twice the segment, and the area is 0.
Farthest pair
The two points farthest apart are always corners of the hull. If one of them is not a corner, extend the line from the other point through it until it leaves the hull: the exit point is farther away and lies on a side, and one end of that side is at least as far again. So it is enough to check all pairs of corners, in O(h^2) time for corners. With small coordinates the hull is small too: with |x|, |y| \le 1000 it has fewer than a thousand corners. When all points can be corners, use rotating calipers, which take .
Correctness proof
Look at the lower walk after it has handled the first points in sorted order. The invariant is that the stack holds the lower hull of these points, from the leftmost to the newest, turning left at every point.
A new point is the rightmost so far, so the lower hull of the first i + 1 points ends at it, and it belongs on the stack.
A point is popped when the point under it and don't turn left with it. Since is to the left of and is to the right, lies on or above the segment from to , as point 2 lies above the segment from 1 to 5 in Fig. 2. The lower hull runs on or below that segment, and new points can only pull it further down, so never becomes its corner.
When the popping stops, the last turn is left and all earlier turns were left already. So the stack turns left at every point, and no point seen so far lies below it. A path from the leftmost to the rightmost point with these two properties is exactly the lower hull, so every point left on the stack is a corner.
The same argument from right to left gives the upper hull. Both halves meet at the leftmost and the rightmost points, so together they are the whole hull.
Common mistakes
Popping with
ifinstead ofwhile. On the 8 points above this leaves point 2 on the lower hull, as the red line in Fig. 2 shows. Keep popping while the turn is not left.Sorting by
xonly. For the input (0, 2), (0, 0), (0, 1), (1, 2), the three points withx = 0can stay in input order, and the result (0, 2), (0, 1), (1, 2) loses the corner (0, 0). Compareywhenxis equal.Letting the upper walk pop below the lower hull. On the 8 points above, its first check is 7, 8, 7, which lie on one line, so 8 is popped and the program prints (0, 4), (6, 0), (8, 1), (7, 6), (3, 7), losing the corner (9, 4). Pop only while
h.size() > lower.Forgetting to remove repeated points. For the input (5, 5), (5, 5), the program then prints the point twice. Remove them with
uniqueafter the sort.
Similar algorithms
A monotonic stack runs the same pop-then-push loop on an array, popping by value instead of by the direction of a turn.
The Graham scan sorts the points by angle around the lowest point and makes one walk with the same pop rule, also in O(n \log n). Gift wrapping (the Jarvis march) picks one corner at a time in for corners.
Rotating calipers walk around the hull's corners to find the farthest pair of points or the minimum width in .
Practice
Very easy · Convex Hull
Very easy · Geometry
Medium · Convex Hull
Hard · Geometry · Convex Hull
Hard · Geometry
Easy · Geometry · Convex Hull
Hard · Geometry · Convex Hull
Medium · Convex Hull · Geometry
Very easy · Geometry