rt,自己造的数据和样例都可以通过了。
bool begmem;
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 300010;
using POD = pair<double, double>;
#define x first
#define y second
double cross(POD q, POD b) {
return q.x * b.y - q.y * b.x;
}
POD operator-(const POD &l, const POD &r) {
return {l.x - r.x, l.y - r.y};
}
double dist(POD q, POD b) {
return sqrt((q.x - b.x) * (q.x - b.x) + (q.y - b.y) * (q.y - b.y));
}
double area(POD q, POD b, POD c) {
return abs(cross(b - q, c - q));
}
POD q[N];
int n, top, stk[N], used[N];
// vector<POD> andrew() {
// sort(q, q + n);
// int top = 0;
// for (int i = 0; i < n; ++i) {
// while (top >= 2 && area(q[stk[top - 1]], q[stk[top]], q[i]) <= 0) used[stk[top--]] = 0;
// stk[++top] = i, used[i] = 1;
// }
// used[0] = 0;
// for (int i = n - 1; ~i; --i)
// if (!used[i]) {
// while (top >= 2 && area(q[stk[top - 1]], q[stk[top]], q[i]) <= 0) --top;
// stk[++top] = i;
// }
// vector<POD> res;
// for (int i = 1; i <= top; ++i) res.emplace_back(q[stk[i]]);
// return res;
// }
vector<POD> andrew() {
int top=0;
stk[0]=1;
stk[1]=2;
for(int i=3;i<=n;++i){
while(top&&area(q[stk[top-1]],q[stk[top]],q[i])<=0)--top;
stk[++top]=i;
}
stk[++top]=n-1;
for(int i=n-2;i>0;--i){
while(top>1&&area(q[stk[top-1]],q[stk[top]],q[i])<=0)--top;
stk[++top]=i;
}
vector<POD> res;
for(int i=1;i<=top;++i)res.emplace_back(q[stk[i]]);
return res;
}
struct Lin {
POD x, y;
} ;
int len(POD x) {
return x.first * x.first + x.second * x.second;
}
double tolin(POD p, Lin x) {
POD p1 = x.y, p2 = p - x.x;
return abs(cross(p1, p2));
}
double roating(vector<POD> tubao) {
if (tubao.size() == 3)
return len(tubao[1] - tubao[0]);
int p = 0, mx = 0;
for (int i = 0; i < (int)tubao.size() - 1; ++i) {
POD l1 = tubao[i + 1] - tubao[i];
while (abs(cross(l1, tubao[p] - tubao[i])) <= abs(cross(tubao[p + 1] - tubao[i], l1)))
p = (p + 1) % ((int)tubao.size() - 1);
mx = max({mx, len(tubao[i] - tubao[p]), len(tubao[i + 1] - tubao[p])});
}
return mx;
}
double area(vector<POD> tubao) {
tubao.pop_back();
if (tubao.size() >= 3) {
double mx = 0;
for (int i = 0; i < tubao.size(); ++i) {
int p1 = (i + 1) % tubao.size(), p2 = (i + 3) % tubao.size();
for (int j = (i + 2) % tubao.size(); j != i; j = (j + 1) % tubao.size()) {
while (p1 != j && area(tubao[i], tubao[j], tubao[p1]) < area(tubao[i], tubao[j], tubao[p1 + 1])) p1 = (p1 + 1) % tubao.size();
while (p2 != i && area(tubao[i], tubao[j], tubao[p2]) < area(tubao[i], tubao[j], tubao[p2 + 1])) p2 = (p2 + 1) % tubao.size();
mx = max(mx, area(tubao[i], tubao[j], tubao[p1]) + area(tubao[i], tubao[j], tubao[p2]));
// printf("%lf %lf %lf %lf %lf %lf %lf %lf: ", tubao[i].first, tubao[i].second, tubao[j].first, tubao[j].second, tubao[p1].first, tubao[p1].second, tubao[p2].first, tubao[p2].second);
// printf("%lld %lld %lld %lld %lf %lf\n", i, j, p1, p2, area(tubao[i], tubao[j], tubao[p1]), area(tubao[i], tubao[j], tubao[p2]));
}
}
return mx;
} else {
return 0;
}
}
void solveqwq() {
scanf("%lld", &n);
for (int i = 1; i <= n; ++i)
scanf("%lf%lf", &q[i].x, &q[i].y);
printf("%.3lf\n", area(andrew()) / 2);
}
void calcqwq();
signed main() {
atexit(calcqwq);
int T = 1;
clock_t stk = clock();
while (T--) solveqwq();
clock_t ed = clock();
fprintf(stderr, "Time Used %.5lf second(s).\n", 1. * (ed - stk) / CLOCKS_PER_SEC);
}
bool endmem;
void calcqwq() {
fprintf(stderr, "Memory = %.5lf\n", (&begmem - &endmem) / 1048576.);
}
/*
5
0 0
1 0
2 1
2 2
1 2
*/