---
tags: codebook
---

# convex hull

int n; cin >> n;
V<P<double>> v(n);
for (auto& i : v)
	cin >> i.first >> i.second;
sort(v.begin(), v.end());
V<P<double>> s{v[0], v[1]};
auto cross = [&](P<double> p1, P<double> p2, P<double> p3) {
	return (p2.first - p1.first) * (p3.second - p1.second)
	       - (p2.second - p1.second) * (p3.first - p1.first);
};
for (int i = 2; i < n; i++) {
	while (s.size() >= 2 && cross(s.rbegin()[1], s.rbegin()[0], v[i]) <= 0)
		s.pop_back();
	s.push_back(v[i]);
}
for (int i = n - 2, t = s.size() + 1; i >= 0; i--) {
	while (int(s.size()) >= t && cross(s.rbegin()[1], s.rbegin()[0], v[i]) <= 0)
		s.pop_back();
	s.push_back(v[i]);
}
s.pop_back();