Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- using ll = long long;
- using ld = long double;
- using pii = pair<int, int>;
- const int maxN = 3e3 + 5;
- const int INF = 1e9 + 7;
- const double eps = 1e-8;
- struct point {
- long long x, y;
- };
- bool xetx(point a, point b) { return (a.x < b.x) || (a.x == b.x && a.y < b.y); }
- bool xety(point a, point b) { return (a.y < b.y) || (a.y == b.y && a.x < b.x); }
- ll area(point a, point b, point c) {
- return a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y);
- }
- bool isCW(point a, point b, point c) { return area(a, b, c) < 0; }
- bool isCCW(point a, point b, point c) { return area(a, b, c) > 0; }
- int n;
- point p[maxN];
- ll ans = 0;
- vector<point> hull;
- void convexHull(vector<point> &a) {
- vector<point> up, down;
- up.push_back(p[1]);
- down.push_back(p[1]);
- for (int i = 1; i <= n; ++i) {
- if (i == n || isCW(p[1], p[i], p[n])) {
- while (up.size() > 1 && !isCW(up[up.size() - 2], up[up.size() - 1], p[i]))
- up.pop_back();
- up.push_back(p[i]);
- }
- if (i == n || isCCW(p[1], p[i], p[n])) {
- while (down.size() > 1 && !isCCW(down[down.size() - 2], down[down.size() - 1], p[i]))
- down.pop_back();
- down.push_back(p[i]);
- }
- }
- for (int i = 0; i < up.size(); ++i)
- a.push_back(up[i]);
- for (int i = down.size() - 2; i > 0; --i)
- a.push_back(down[i]);
- }
- void solve() {
- for (int i = 0; i < hull.size() - 2; ++i) {
- int k = i + 2;
- for (int j = i + 1; j < hull.size() - 1; ++j) {
- if (j >= k) k = j + 1;
- ll cur = abs(area(hull[i], hull[j], hull[k]));
- while (k < hull.size() - 1) {
- ll tmp = abs(area(hull[i], hull[j], hull[k + 1]));
- if (cur < tmp) cur = tmp, ++k;
- else break;
- }
- ans = max(ans, cur);
- }
- }
- cout << (ans >> 1LL) << (ans % 2 ? ".5\n" : ".0\n");
- }
- int main() {
- #ifdef LOCAL
- freopen("in1.txt", "r", stdin);
- #else
- freopen("TRILAND.inp", "r", stdin);
- freopen("TRILAND.out", "w", stdout);
- #endif
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- cin >> n;
- for (int i = 1; i <= n; ++i)
- cin >> p[i].x >> p[i].y;
- sort(p + 1, p + n + 1, [](point a, point b) {
- if (a.x == b.x) return a.y < b.y;
- return a.x < b.x;
- });
- convexHull(hull);
- solve();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment