ConvexHull

75mm Returns a vector of the points of the convex hull in counter-clockwise order. Points on the edge of the hull between two other points are not considered part of the hull. 15mm

Time: O(n log n) 13 lines stress-tested, tested with kattis:convexhull

Needs: "Point.h"

content/geometry/ConvexHull.h — Stjepan Glavina, chilli, source: https://github.com/stjepang/snippets/blob/master/convex_hull.cpp

typedef Point<ll> P;
vector<P> convexHull(vector<P> pts) {
	if (sz(pts) <= 1) return pts;
	sort(all(pts));
	vector<P> h(sz(pts)+1);
	int s = 0, t = 0;
	for (int it = 2; it--; s = --t, reverse(all(pts)))
		for (P p : pts) {
			while (t >= s + 2 && h[t-2].cross(h[t-1], p) <= 0) t--;
			h[t++] = p;
		}
	return {h.begin(), h.begin() + t - (t == 2 && h[0] == h[1])};
}