Submission #1280377

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280377		daotuankhoi	SIR (COI15_sir)	C++20	100 / 100	121 ms	26328 KiB

sir

#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define ll long long

#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif

template <class T> bool ckmax(T &a, T b) { return a < b ? (a = b, true) : false; }
template <class T> bool ckmin(T &a, T b) { return a > b ? (a = b, true) : false; }

struct Vec {
    ll x, y;
    Vec(ll _x = 0, ll _y = 0) : x(_x), y(_y) {}
    Vec operator-(Vec o) {
        return Vec(x - o.x, y - o.y);
    }
    bool operator<(Vec o) {
        return (x < o.x || (x == o.x && y < o.y));
    }
    bool operator==(Vec o) { return x == o.x && y == o.y; }
};

using Point = Vec;
ll cross(Vec a, Vec b) {
    return (a.x * b.y) - (a.y * b.x);
}

bool cw(Point a, Point b, Point c) {
    Vec ab = b - a;
    Vec ac = c - a;
    return cross(ab, ac) > 0;
}

bool chk(Point a, Point b, Point c, Point d) {
    if (a == b) return 1;
    if (cw(a, b, d) || cw(b, c, d) || cw(c, a, d)) return 1;
    return 0;
}

ll area(Point a, Point b, Point c) {
    array<Point, 4> e;
    e[0] = a; e[1] = b, e[2] = c, e[3] = a;
    ll ans = 0;
    for (int i = 0; i < 3; i++) {
        ans += (e[i].x * e[i+1].y) - (e[i+1].x * e[i].y);
    }
    return abs(ans);
}

const int MAXN = 3e5 + 5;
Point a[MAXN], d[MAXN];

int main() {
    #define NAME "test"
    if (fopen(NAME".inp", "r")) {
        freopen(NAME".inp", "r", stdin);
        freopen(NAME".out", "w", stdout);
    }
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n; cin >> n;
    for (int i = 0; i < n; i++) cin >> d[i].x >> d[i].y;
    reverse(d, d + n);
    int m; cin >> m;
    for (int i = 1; i <= m; i++) cin >> a[i].x >> a[i].y;
    sort(a + 1, a + m + 1);
    vector<Point> hull;
    hull.emplace_back(a[1]);
    for (int i = 2; i <= m; i++) {
        while ((int)hull.size() >= 2 && cw(hull[(int)hull.size() - 2], hull[(int)hull.size() - 1], a[i])) hull.pop_back();
        hull.emplace_back(a[i]);
    }
    for (int i = m - 1; i >= 1; i--) {
        while ((int)hull.size() >= 2 && cw(hull[(int)hull.size() - 2], hull[(int)hull.size() - 1], a[i])) hull.pop_back();
        hull.emplace_back(a[i]);
    }
    if (m > 1) hull.pop_back();
    m = hull.size();
    ll ans = 0, s = 0;

    int cur = 0, tt = 1;
    for (int i = 0; i < m; i++) if (cw(d[0], hull[cur], hull[i])) cur = i;
    for (int i = 0; i < n; i++) {
        while (cw(d[i], hull[cur], hull[(cur + 1) % m])) {
            cur++;
            if (cur >= m) cur -= m;
        }
        while (chk(d[i], d[tt], d[(tt + 1) % n], hull[cur])) {
            s += area(d[i], d[tt], d[(tt + 1) % n]);
            tt++;
            if (tt >= n) tt -= n;
        }
        debug(tt, s);
        ckmax(ans, s);
        s -= area(d[i], d[(i + 1) % n], d[tt]);
    }
    cout << ans << '\n';
    return 0;
}

Compilation message (stderr)

sir.cpp: In function 'int main()':
sir.cpp:63:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |         freopen(NAME".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sir.cpp:64:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |         freopen(NAME".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 12 / 12
• Subtask 2: 39 / 39
• Subtask 3: 49 / 49