Submission #487326

#	Time	Username	Problem	Language	Result	Execution time	Memory
487326		Zunnn	SIR (COI15_sir)	C++14	61 / 100	182 ms	20444 KiB

sir

#include "bits/stdc++.h"
#define ll long long
#define giuncute ios_base::sync_with_stdio(0) , cin.tie(0);
#define pl pair<ll,ll>
#define FOR(i, a, b) for(int i = a; i < b; ++i)
#define REP(i, n) FOR(i, 0, n)
#define sz(x) ((int) x.size())
#define pb(x) push_back(x)
#define fi first
#define se second
using namespace std;
const ll maxn = 5e5 + 7;
const ll oo = 1e18 ;
ll n  , m ;
pl u[maxn]  , v[maxn];
vector<pl> hull;
ll ccw(pl A, pl B, pl C)
{
  return (ll)A.fi * (B.se - C.se) + (ll)B.fi * (C.se - A.se) + (ll)C.fi * (A.se - B.se);
}
ll nextN(ll x)
{
    if(x == n - 1) return 0;
    return x + 1;
}
ll nextM(ll x)
{
    if(x == hull.size() - 1) return 0;
    return x + 1;
}

void solve()
{
    ll sol = 0, ans = 0 , r = 1 ,curr = 0;
    REP(l, n)
    {
    while(ccw(u[l], hull[curr], hull[nextM(curr)]) < 0) curr = nextM(curr);
    while(ccw(u[l], u[nextN(r)], hull[curr]) > 0)
    {
        if(l != r) ans += abs( ccw(u[l], u[r], u[nextN(r)]) );
        r = nextN(r);
    }
    sol = max(sol, ans);
    if(r != nextN(l) && r != l) ans -= abs( ccw(u[l], u[nextN(l)], u[r]) );
    }
    cout << sol;
}
int main()
{
    giuncute;
    cin >> n ;
    for (int i = 0 ; i < n ; i++) cin >> u[i].fi >> u[i].se;
    cin >> m ;
    for (int i = 0 ; i < m ; i++) cin >> v[i].fi >> v[i].se;
    vector <pl> hull2;  
    sort(v, v + m);
    for (int i = 0 ; i < m ; i++)
    {
        while(sz(hull) > 1 && ccw(hull[sz(hull) - 2], hull.back(), v[i]) >= 0)
        hull.pop_back();
        hull.pb(v[i]);
    }
    for(int i = m - 1; i >= 0; --i)
    {
        while(sz(hull2) > 1 && ccw(hull2[sz(hull2) - 2], hull2.back(), v[i]) >= 0)
            hull2.pop_back();
        hull2.pb(v[i]);
    }
    FOR(i, 1, sz(hull2) - 1) hull.pb(hull2[i]);
    reverse(hull.begin(), hull.end());
    solve();
}

Compilation message (stderr)

sir.cpp: In function 'long long int nextM(long long int)':
sir.cpp:28:10: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     if(x == hull.size() - 1) return 0;
      |        ~~^~~~~~~~~~~~~~~~~~

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