oj.uz

Submission #487326

# Submission time Handle Problem Language Result Execution time Memory
487326 2021-11-15T07:31:14 Z Zunnn SIR (COI15_sir) C++14
61 / 100
 182 ms 20444 KB 
#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

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.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct

Subtask #2
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 2 ms 588 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Incorrect 1 ms 576 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 20444 KB Output is correct
2 Correct 182 ms 18764 KB Output is correct
3 Correct 108 ms 19904 KB Output is correct
4 Correct 32 ms 5724 KB Output is correct
5 Correct 99 ms 16712 KB Output is correct
6 Correct 101 ms 14628 KB Output is correct