Submission #1308074

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308074		gkos5678	SIR (COI15_sir)	C++20	51 / 100	1096 ms	15732 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;
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);
}

ll slj(ll a, ll md){
    a++;
    if (a == md)
        a = 0;
    return a;
}

ll pro(ll a, ll md){
    a--;
    if (a == -1)
        a = md - 1;
    return a;
}

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 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();

    ll mx = 0;
    ll ans = 0;
    int trr = 0, tr = 0;
    ll uk = 0;
    for (int i = 0; i < n; i++){
        if (i > 0)
            uk -= ccw(p[i - 1], p[i], p[trr]);
        while(true){
            trr = slj(trr, n);
            int prtr = tr, brit = 0;
            while(brit < m && ccw(p[i], p[trr], r[slj(tr, m)]) <= ccw(p[i], p[trr], r[tr]))
                tr = slj(tr, m), brit++;
            if (ccw(p[i], p[trr], r[tr]) <= 0){
                tr = prtr;
                trr = pro(trr, n);
                break;
            }
            uk += ccw(p[i], p[pro(trr, n)], p[trr]);
        }
        ans = max(ans, uk);
    }
    cout << ans << "\n";
    return 0;
}

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