monotone.cpp

// O(N log N) Monotone Chains algorithm for 2d convex hull.
// Gives the hull in counterclockwise order from the leftmost point, which is repeated at the end. Minimizes the number of points on the hull when collinear points exist.
long long cross(pair<int, int> A, pair<int, int> B, pair<int, int> C) {
	return (B.first - A.first)*(C.second - A.second)
	     - (B.second - A.second)*(C.first - A.first);
}
// The hull is returned in param "hull"
void convex_hull(vector<pair<int, int> > pts, vector<pair<int, int> >& hull) {
	hull.clear(); sort(pts.begin(), pts.end());
	for (int i = 0; i < pts.size(); i++) {
		while (hull.size() >= 2 && cross(hull[hull.size()-2], hull.back(), pts[i]) <= 0) {
			hull.pop_back();
		}
		hull.push_back(pts[i]);
	}
	int s = hull.size();
	for (int i = pts.size()-2; i >= 0; i--) {
		while (hull.size() >= s+1 && cross(hull[hull.size()-2], hull.back(), pts[i]) <= 0) {
			hull.pop_back();
		}
		hull.push_back(pts[i]);
	}
}