---
tags: codebook
---

# biggest triangle (旋轉卡尺)

convex hull + two pointer

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();
auto det = [&](int a, int b, int c) {
	V<V<double>> arr{
		{s[a].first , s[b].first , s[c].first },
		{s[a].second, s[b].second, s[c].second}
	};
	double ret = 0;
	for (int i = 0; i < 3; i++) {
		ret += arr[0][i] * arr[1][(i + 1) % 3];
		ret -= arr[1][i] * arr[0][(i + 1) % 3];
	}
	return ret / 2;
};
double ans = 0;
for (int i = 0, end = s.size(); i < end; i++) {
	for (int j = 1, end = s.size(), k = 2; j < end; j++) {
		while (det(i, j, k) < det(i, j, k + 1)) k++;
		ans = max(ans, det(i, j, k));
	}
}
cout << fixed << setprecision(6) << ans << endl;