Graham Scan sorts points by polar angle around a pivot, then uses a stack to keep only left turns. Points causing non-left turns are removed. Final stack forms the convex hull in counterclockwise order.
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);
}
vector<P> convexHull(vector<P> pts) {
sort(pts.begin(), pts.end(), [](const P& a, const P& b) {
return a.x == b.x ? a.y < b.y : a.x < b.x;
});
vector<P> h;
for (auto& p : pts) {
while (h.size() >= 2 && cross(h[h.size()-2], h.back(), p) <= 0) h.pop_back();
h.push_back(p);
}
int t = h.size() + 1;
for (int i = (int)pts.size() - 2; i >= 0; i--) {
while ((int)h.size() >= t && cross(h[h.size()-2], h.back(), pts[i]) <= 0) h.pop_back();
h.push_back(pts[i]);
}
h.pop_back();
return h;
}Cross product sign decides left-turn vs right-turn during hull construction.
Pop while last turn is non-left; keep boundary points only.
Sorting dominates runtime, giving O(n log n).
Quiz coming soon for this algorithm.