DuongNhi99

TRILAND

Jan 10th, 2022
756
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.50 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. using ll = long long;
  5. using ld = long double;
  6. using pii = pair<int, int>;
  7.  
  8. const int maxN = 3e3 + 5;
  9. const int INF = 1e9 + 7;
  10. const double eps = 1e-8;
  11.  
  12. struct point {
  13.     long long x, y;
  14. };
  15.  
  16. bool xetx(point a, point b) { return (a.x < b.x) || (a.x == b.x && a.y < b.y); }
  17. bool xety(point a, point b) { return (a.y < b.y) || (a.y == b.y && a.x < b.x); }
  18.  
  19. ll area(point a, point b, point c) {
  20.     return a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y);
  21. }
  22.  
  23. bool isCW(point a, point b, point c) { return area(a, b, c) < 0; }
  24. bool isCCW(point a, point b, point c) { return area(a, b, c) > 0; }
  25.  
  26. int n;
  27. point p[maxN];
  28.  
  29. ll ans = 0;
  30. vector<point> hull;
  31.  
  32. void convexHull(vector<point> &a) {
  33.     vector<point> up, down;
  34.     up.push_back(p[1]);
  35.     down.push_back(p[1]);
  36.  
  37.     for (int i = 1; i <= n; ++i) {
  38.         if (i == n || isCW(p[1], p[i], p[n])) {
  39.             while (up.size() > 1 && !isCW(up[up.size() - 2], up[up.size() - 1], p[i]))
  40.                 up.pop_back();
  41.             up.push_back(p[i]);
  42.         }
  43.  
  44.         if (i == n || isCCW(p[1], p[i], p[n])) {
  45.             while (down.size() > 1 && !isCCW(down[down.size() - 2], down[down.size() - 1], p[i]))
  46.                 down.pop_back();
  47.             down.push_back(p[i]);
  48.         }
  49.     }
  50.  
  51.     for (int i = 0; i < up.size(); ++i)
  52.         a.push_back(up[i]);
  53.     for (int i = down.size() - 2; i > 0; --i)
  54.         a.push_back(down[i]);
  55. }
  56.  
  57. void solve() {
  58.     for (int i = 0; i < hull.size() - 2; ++i) {
  59.         int k = i + 2;
  60.         for (int j = i + 1; j < hull.size() - 1; ++j) {
  61.             if (j >= k) k = j + 1;
  62.             ll cur = abs(area(hull[i], hull[j], hull[k]));
  63.             while (k < hull.size() - 1) {
  64.                 ll tmp = abs(area(hull[i], hull[j], hull[k + 1]));
  65.                 if (cur < tmp) cur = tmp, ++k;
  66.                 else break;
  67.             }
  68.             ans = max(ans, cur);
  69.         }
  70.     }
  71.     cout << (ans >> 1LL) << (ans % 2 ? ".5\n" : ".0\n");
  72. }
  73.  
  74. int main() {
  75. #ifdef LOCAL
  76.     freopen("in1.txt", "r", stdin);
  77. #else
  78.     freopen("TRILAND.inp", "r", stdin);
  79.     freopen("TRILAND.out", "w", stdout);
  80. #endif
  81.     ios_base::sync_with_stdio(false);
  82.     cin.tie(nullptr);
  83.  
  84.     cin >> n;
  85.     for (int i = 1; i <= n; ++i)
  86.         cin >> p[i].x >> p[i].y;
  87.     sort(p + 1, p + n + 1, [](point a, point b) {
  88.         if (a.x == b.x) return a.y < b.y;
  89.         return a.x < b.x;
  90.     });
  91.  
  92.     convexHull(hull);
  93.     solve();
  94.  
  95.     return 0;
  96. }
  97.  
Advertisement
Add Comment
Please, Sign In to add comment