#pragma GCC optimize("Ofast") #include using namespace std; typedef long long int ll; typedef unsigned long long int ull; mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); ll myRand(ll B) { return (ull)rng() % B; } inline double time() { return static_cast(chrono::duration_cast(chrono::steady_clock::now().time_since_epoch()).count()) * 1e-9; } const double eps=1e-10; struct point{ ll x,y; point() {} point(ll x,ll y): x(x), y(y) {} point& operator-=(const point &p){ x -= p.x; y -= p.y; return *this; } point& operator+=(const point &p){ x += p.x; y += p.y; return *this; } point& operator*=(double d){ x *= d; y *= d; return *this; } point& operator/=(double d){ x /= d; y /= d; return *this; } const point operator+ (const point& p) const; const point operator- (const point& p) const; const point operator* (double d) const; const point operator/ (double d) const; }; const point point::operator+ (const point& p) const{ point res(*this); return res += p; } const point point::operator- (const point& p) const{ point res(*this); return res -= p; } const point point::operator* (double d) const{ point res(*this); return res *= d; } const point point::operator/ (double d) const{ point res(*this); return res /= d; } struct line{ point A,B; line() {} line(point A, point B): A(A), B(B) {} }; // A+B point sum(point A,point B){ A.x+=B.x; A.y+=B.y; return A; } // A-B point sub(point A,point B){ A.x-=B.x; A.y-=B.y; return A; } // A to B point vec(line L){ return (L.B - L.A); } ll dot(point a,point b){ return a.x*b.x+a.y*b.y; } ll cross(point a,point b){ return a.x*b.y-a.y*b.x; } int ccw(point a,point b,point c){ b={b.x-a.x,b.y-a.y}; c={c.x-a.x,c.y-a.y}; if(cross(b,c)>eps)return 1; // a,b,c反時計回り if(cross(b,c)<-eps)return -1; // a,b,c時計周り if(dot(b,c)<-eps)return 2; // c,a,b 一直線 if((b.x*b.x+b.y*b.y)<(c.x*c.x+c.y*c.y))return -2; // a,b,c 一直線 return 0; // a,c,b 一直線 } // 凸包 // AOJ 2827 vector convex_hull(vector ps){ int n = ps.size(); int k = 0; // 凸包の頂点数 sort(ps.begin(), ps.end(), [&](auto p, auto q){ if(p.x < q.x - eps) return true; if(p.x > q.x + eps) return false; return p.y < q.y; }); vector qs(2*n); // 構築中の凸包 for(int i=0;i=2&&ccw(qs[k-2],qs[k-1],ps[i])<=0) --k; } for(int i=n-2,t=k+1;i>=0;qs[k++]=ps[i--]){ while(k>=t&&ccw(qs[k-2],qs[k-1],ps[i])<=0) --k; } qs.resize(k-1); return qs; } // AOJ-2160 // 多角形の符号付き面積(反時計回りが正) ll area(vector g){ ll res=0.0; for(int i=0;i+1> n; vector p(n); for (int i = 0; i < n; ++i) { int x,y; cin >> x >> y; p[i] = point(x,y); } auto ps = convex_hull(p); if (ps.size() >= 4) { p = ps; } // p = convex_hull(p); ll res = 0; n = p.size(); for (int i = 0; i < n; ++i) { for (int j = i+1; j < n; ++j) { for (int k = j+1; k < n; ++k) { for (int l = k+1; l < n; ++l) { res = max(res, area(vector{p[i],p[j],p[k],p[l],p[i]})); } } } } cout << res << endl; }