/* -*- coding: utf-8 -*- * * 2331.cc: No.2331 Maximum Quadrilateral - yukicoder */ #include #include #include using namespace std; /* constant */ /* typedef */ template struct Pt { T x, y; Pt() {} Pt(T _x, T _y) : x(_x), y(_y) {} Pt(const Pt &p) : x(p.x), y(p.y) {} Pt operator+(const Pt p) const { return Pt(x + p.x, y + p.y); } Pt operator-() const { return Pt(-x, -y); } Pt operator-(const Pt p) const { return Pt(x - p.x, y - p.y); } Pt operator*(T t) const { return Pt(x * t, y * t); } Pt operator/(T t) const { return Pt(x / t, y / t); } T dot(Pt v) const { return x * v.x + y * v.y; } T cross(Pt v) const { return x * v.y - y * v.x; } Pt mid(const Pt p) { return Pt((x + p.x) / 2, (y + p.y) / 2); } T d2() { return x * x + y * y; } double d() { return sqrt(d2()); } bool operator==(const Pt pt) const { return x == pt.x && y == pt.y; } bool operator<(const Pt &pt) const { return x < pt.x || (x == pt.x && y < pt.y); } }; typedef Pt pt; typedef vector vpt; /* global variables */ /* subroutines */ void convex_hull(const vpt& ps, vpt& chs) { int n = ps.size(); vpt lhs, uhs; lhs.push_back(ps[0]); lhs.push_back(ps[1]); for (int i = 2; i < n; i++) { while (lhs.size() >= 2) { int ln = lhs.size(); pt &lh0 = lhs[ln - 2], &lh1 = lhs[ln - 1]; if ((lh1 - lh0).cross(ps[i] - lh1) > 0) break; lhs.pop_back(); } lhs.push_back(ps[i]); } uhs.push_back(ps[n - 1]); uhs.push_back(ps[n - 2]); for (int i = n - 3; i >= 0; i--) { while (uhs.size() >= 2) { int un = uhs.size(); pt &uh0 = uhs[un - 2], &uh1 = uhs[un - 1]; if ((uh1 - uh0).cross(ps[i] - uh1) > 0) break; uhs.pop_back(); } uhs.push_back(ps[i]); } lhs.pop_back(); uhs.pop_back(); chs.clear(); chs.reserve(lhs.size() + uhs.size()); chs.assign(lhs.begin(), lhs.end()); chs.insert(chs.end(), uhs.begin(), uhs.end()); } inline int area(pt &p0, pt &p1, pt &p2) { return abs((p1 - p0).cross(p2 - p0)); } int tsearch(vpt &chs, int i, int j0, int l0, int r0) { int m = chs.size(), j = (i + j0) % m; while (l0 + 2 < r0) { int kk0 = (l0 * 2 + r0) / 3; int kk1 = (l0 + r0 * 2) / 3; int s0 = area(chs[i], chs[j], chs[(i + kk0) % m]); int s1 = area(chs[i], chs[j], chs[(i + kk1) % m]); if (s0 < s1) l0 = kk0; else r0 = kk1; } int maxs = 0; for (int k = l0; k <= r0; k++) maxs = max(maxs, area(chs[i], chs[j], chs[(i + k) % m])); return maxs; } /* main */ int main() { int n; scanf("%d", &n); vpt ps(n); for (int i = 0; i < n; i++) scanf("%d%d", &ps[i].x, &ps[i].y); sort(ps.begin(), ps.end()); vpt chs; convex_hull(ps, chs); int m = chs.size(); //printf("m=%d\n", m); //for (auto &p: chs) printf("%d, %d\n", p.x, p.y); int maxs = 0; for (int i = 0; i < m; i++) { for (int j0 = 2; j0 + 2 <= m; j0++) { int t0 = tsearch(chs, i, j0, 1, j0 - 1); int t1 = tsearch(chs, i, j0, j0 + 1, m - 1); maxs = max(maxs, t0 + t1); } } printf("%d\n", maxs); return 0; }