Submission #1307914

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307914		gkos5678	SIR (COI15_sir)	C++20	0 / 100	189 ms	15740 KiB

sir

#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define ppb pop_back
#define all(v) v.begin(), v.end()
#define ff first
#define ss second

typedef long long ll;
typedef pair<ll, ll> ii;
typedef vector<ii> vii;

const int maxn = 3e5 + 7;
const int inf = 1e9;

int n, m;
ll ps1[maxn], ps2[maxn];
ii pv;
vii p, r, ch;

ll ccw(ii a, ii b, ii c){
    return a.ff * (b.ss - c.ss) + b.ff * (c.ss - a.ss) + c.ff * (a.ss - b.ss);
}

bool comb(ii a, ii b){
    if (a == pv)
        return 1;
    if (b == pv)
        return 0;
    ll f = ccw(pv, a, b);
    if (f > 0)
        return 1;
    if (f < 0)
        return 0;
    return (abs(a.ff - pv.ff) > (b.ff - pv.ff));
}

vii convexhull(vii po){
    if (po.size() < 3)
        return po;
    sort(all(po));
    pv = po[0];
    sort(all(po), comb);
    ch.clear();
    ch.pb(po[0]);
    ch.pb(po[1]);
    int trsz = 1;
    for (int i = 2; i < po.size(); i++){
        while(ch.size() > 1 && ccw(ch[trsz - 1], ch[trsz], po[i]) < 0){
            trsz--;
            ch.ppb();
        }
        if (trsz == 0 || ccw(ch[trsz - 1], ch[trsz], po[i]) > 0){
            ch.pb(po[i]);
            trsz++;
        }
    }
    return ch;
}

int bs(int inp, int inr){
    int le = 2, ri = n - 1;
    while(le < ri){
        int mi = (le + ri) / 2;
        ll f = ccw(p[inp], p[(inp + mi) % n], r[inr]);
        if (f > 0)
            le = mi + 1;
        else
            ri = mi;
    }
    return le;
}

ll sum1(int le, int ri){
    le %= n, ri %= n;
    ll ret = ps1[ri] - ps1[(le + n - 1) % n];
    if (ri < le || le == 0)
        ret += ps1[n - 1];
    return ret;
}

ll sum2(int le, int ri){
    le %= n, ri %= n;
    ll ret = ps2[ri] - ps2[(le + n - 1) % n];
    if (ri < le || le == 0)
        ret += ps2[n - 1];
    return ret;
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> n;
	p.resize(n);
	for (int i = 0; i < n; i++)
        cin >> p[i].ff >> p[i].ss;
    cin >> m;
    r.resize(m);
    for (int i = 0; i < m; i++)
        cin >> r[i].ff >> r[i].ss;

    r = convexhull(r);
    m = r.size();
    int mn = inf, tr = -1;
    bool svj = 1;
    for (int i = 0; i < m; i++){
        int le = bs(0, i);
        if (le < mn){
            mn = le;
            tr = i;
        }
    }
    ll mx = 0;
    ps1[0] = p[0].ff * p[1].ss;
    for (int i = 1; i < n; i++)
        ps1[i] = ps1[i - 1] + p[i].ff * p[(i + 1) % n].ss;
    ps2[0] = p[0].ff * p[n - 1].ss;
    for (int i = 1; i < n; i++)
        ps2[i] = ps2[i - 1] + p[i].ff * p[i - 1].ss;
    ll ans = 0;
    for (int i = 0; i < n; i++){
        int brit = 0;
        while(bs(i, (tr + 1) % m) <= bs(i, tr) && brit < m){
            tr = (tr + 1) % m;
            brit++;
        }
        int mx = bs(i, tr) - 1;
        ll pov = sum1(i, i + mx - 1) + p[(i + mx) % n].ff * p[i].ss;
        pov -= sum2(i + 1, i + mx) + p[i].ff * p[(i + mx) % n].ss;
        ans = max(ans, pov);
    }
    cout << ans << "\n";
    return 0;
}

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