Submission #1271203

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271203		dosts	SIR (COI15_sir)	C++20	0 / 100	115 ms	10924 KiB

sir

#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#define int long long
#define pii pair<int,int>
#define vi vector<int>
#define ff first
#define ss second
#define sp << " " <<
#define all(x) x.begin(),x.end()
#define big(x) ((int)(x.size()))
using namespace std;
const int MOD = 1e9+7, LIM = 1e6+1, inf = 2e9;

const int N = 1e5+1;

int cross(pii p1,pii p2,pii p3) {
   p2.ff-=p1.ff,p3.ff-=p1.ff;
   p2.ss-=p1.ss,p3.ss-=p1.ss;
   return p3.ff*p2.ss-p2.ff*p3.ss; 
}

vector<pii> chull(vector<pii>& pts) {
    int n = big(pts);
    sort(all(pts));
    deque<pii> dq;
    dq.push_back(pts[0]);
    for (int i=1;i<n;i++) {
        while (big(dq) > 1 && cross(dq[big(dq)-2],dq.back(),pts[i]) <= 0) {
            dq.pop_back();
        }
        dq.push_back(pts[i]);
    }
    dq.pop_back();
    for (int i = n-1;i>=0;i--) {
        while (big(dq) > 1 && cross(dq[big(dq)-2],dq.back(),pts[i]) <= 0) {
            dq.pop_back();
        }
        dq.push_back(pts[i]);
    }
    if (n > 1) dq.pop_back();
    return vector<pii>(all(dq));
}


void solve() {
    int n;
    cin >> n;
    vector<pii> pizza(n);
    for (auto& p : pizza) cin >> p.ff >> p.ss;
    int m;
    cin >> m;
    vector<pii> peppers(m);
    for (auto& p : peppers) cin >> p.ff >> p.ss;
    reverse(all(pizza));
    peppers = chull(peppers);
    m = big(peppers);
    int ptr=0;
    for (int i = 0;i<m;i++) {
        if (cross(pizza[0],peppers[(i+m-1)%m],peppers[i]) > 0 && cross(pizza[0],peppers[i],peppers[(i+1)%m]) <= 0) {
            ptr = i;
            break;
        }
    }
    int j = 0;
    int ans = 0;
    int sm = 0;
    for (int i = 0,iter = n;iter;i=(i+n-1)%n,iter--) {
        while (ptr != (ptr+1)%m && cross(pizza[i],peppers[ptr],peppers[(ptr+1)%m]) > 0) {
            ptr=(ptr+1)%m;
        }
        while ((j+n-1)%n != i && cross(pizza[i],peppers[ptr],pizza[(j+n-1)%n]) > 0) {
            sm+=abs(cross(pizza[i],pizza[(j+n-1)%n],pizza[j]));
            j=(j+n-1)%n;
        }
        ans = max(ans,sm);
        sm-=abs(cross(pizza[i],pizza[j],pizza[(i+n-1)%n]));
    }
    cout << ans << '\n';

} 

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    #ifdef Dodi
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    #endif
    int t = 1;
    //cin >> t;
    while (t --> 0) solve();
}

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