Submission #1270933

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270933		dosts	SIR (COI15_sir)	C++20	100 / 100	116 ms	33844 KiB

sir

#include <bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define vi vector<int>
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define sp << " " << 
using namespace std;

const int N =3e6+10,MOD = 1e9+7,inf = 2e18;

bool ccw(pii a,pii b,pii c) {
    return (c.ff-a.ff)*(b.ss-a.ss) < (c.ss-a.ss)*(b.ff-a.ff);
}
bool clockwise(pii a,pii b,pii c) {
    return (c.ff-a.ff)*(b.ss-a.ss) > (c.ss-a.ss)*(b.ff-a.ff);
}
vector<pii> chull(vector<pii> pts) {
    if (pts.size() < 3) return pts;
    sort(all(pts));
    vector<pii> ans;
    vector<pii> stk;
    stk.push_back(pts[0]);
    for (int i = 1;i<pts.size();i++) {
        while (stk.size() > 1 && ccw(stk[stk.size()-2],stk.back(),pts[i])) stk.pop_back();
        stk.push_back(pts[i]);
    }
    stk.pop_back();
    for (auto it : stk) ans.push_back(it);
    stk.clear();
    reverse(all(pts));
    stk.push_back(pts[0]);
    for (int i = 1;i<pts.size();i++) {
        while (stk.size() > 1 && ccw(stk[stk.size()-2],stk.back(),pts[i])) stk.pop_back();
        stk.push_back(pts[i]);
    }
    stk.pop_back();
    for (auto it : stk) ans.push_back(it);
    stk.clear();
    return ans;
}

int area(pii a,pii b,pii c){
    b.ff-=a.ff;
    b.ss-=a.ss;
    c.ff-=a.ff;
    c.ss-=a.ss;
    return abs(b.ff*c.ss-b.ss*c.ff);
}

void solve() {
    int n;
    cin >> n;
    vector<pii> pizza(n);
    for (int i = 0;i<n;i++) cin >> pizza[i].ff >> pizza[i].ss;
    int m;
    cin >> m;
    vector<pii> peppers(m);
    for (int i = 0;i<m;i++) cin >> peppers[i].ff >> peppers[i].ss;
    peppers = chull(peppers);
    reverse(all(peppers));
    m = peppers.size();
    vi tang(n,-1);
    if (m == 1) for (int i =0 ;i<n;i++) tang[i] = 0;
    else {
        for (int i = 0;i<m;i++) {
            if (!clockwise(pizza[0],peppers[i],peppers[(i+1)%m]) && 
                 clockwise(pizza[0],peppers[(i+m-1)%m],peppers[i])) {
                assert(tang[0] == -1);
                tang[0] = i;
            }
        }
        int ptr = tang[0];
        for (int i = 1;i<n;i++) {
            while (clockwise(pizza[i],peppers[ptr],peppers[(ptr+1)%m])) ptr = (ptr+1)%m;
            tang[i] = ptr;
        }
    }

    int ans = 0;
    int cur = 0;
    int take = -1;
    for (int i = 1;i<n;i++) {
        if (clockwise(pizza[0],peppers[tang[0]],pizza[i])) {
            take = i;
        }
    } 
    assert(take != -1);
    for (int i=2;i<=take;i++) {
        cur+=area(pizza[0],pizza[i-1],pizza[i]);
    }
    ans = cur;
    int ptr = take;
    for (int i=1;i<n;i++) {
        int curr = cur;
        cur-=area(pizza[i-1],pizza[i],pizza[ptr]);
        while (clockwise(pizza[i],peppers[tang[i]],pizza[(ptr+1)%n])) {
            cur+=area(pizza[i],pizza[ptr],pizza[(ptr+1)%n]);
            ptr = (ptr+1)%n;
        }
        ans = max(ans,cur);
    }
    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: 12 / 12
• Subtask 2: 39 / 39
• Subtask 3: 49 / 49