Submission #487422

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
487422	2021-11-15T13:08:31 Z	Dirii	SIR (COI15_sir)	C++14	100 / 100	151 ms	15668 KB

sir

// #pragma GCC target("avx2")
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define ll long long
#define cll const ll
#define lp(a, b, c) for(ll a = b; a <= c; ++a)
#define lpd(a, b, c) for(ll a = b; a >= c; --a)
#define vec(a) vector<a>
#define pp(a, b) pair<a, b>
#define EACHCASE lpd(cs, read(), 1)
#define Fname "f"
using namespace std;

template <typename T> inline void Read(T &x){
    x = 0; char c;
    ll dau = 1;
    while(!isdigit(c = getchar())) if(c == '-') dau = -1;
    do{
        x = x * 10 + c - '0';
    } while (isdigit(c = getchar()));
    x *= dau;
}

ll read(){
    ll tmp;
    cin >> tmp;
    return tmp;
}

void giuncute(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
}

void OF(){
    if(fopen(Fname".inp", "r")){
        freopen(Fname".inp", "r", stdin);
        freopen(Fname".out", "w", stdout);
    } else if(fopen(Fname".in", "r")){
        freopen(Fname".in", "r", stdin);
        freopen(Fname".out", "w", stdout);
    }
}

#define point pp(ll, ll)

cll mxn = 3e5 + 4;
ll n, m, ans = 0, cnt[mxn] = {0};
vec(point) cake, pep, conpep;

inline ll valccw(point &a, point &b, point &c){
    return (b.first - a.first) * (c.second - b.second) - (b.second - a.second) * (c.first - b.first);
}

inline int ccw(point &a, point &b, point &c){
    ll val = valccw(a, b, c);
    return (val < 0 ? -1 : (val > 0));
}

void find_con(){
    sort(pep.begin(), pep.end());
    vec(point) up, down;
    up.push_back(pep[0]);
    down.push_back(pep[0]);
    lp(i, 1, pep.size() - 1){
        if(i == pep.size() - 1 || ccw(pep[0], pep[i], pep.back()) <= 0){
            while(up.size() > 1 && ccw(up[up.size() - 2], up.back(), pep[i]) > -1){
                up.pop_back();
            }
            up.push_back(pep[i]);
        }
        if(i == pep.size() - 1 || ccw(pep[0], pep[i], pep.back()) >= 0){
            while(down.size() > 1 && ccw(down[down.size() - 2], down.back(), pep[i]) < 1){
                down.pop_back();
            }
            down.push_back(pep[i]);
        }
    }
    lp(i, 0, down.size() - 1) conpep.push_back(down[i]);
    lpd(i, up.size() - 2, 1) conpep.push_back(up[i]);
}

int main(){
    giuncute();
    #ifndef ONLINE_JUDGE
    OF();
    #endif
    cin >> n;
    lp(i, 1, n){
        point tmp;
        cin >> tmp.first >> tmp.second;
        cake.push_back(tmp);
    }
    cin >> m;
    lp(i, 1, m){
        point tmp;
        cin >> tmp.first >> tmp.second;
        pep.push_back(tmp);
    }
    find_con();
    ll i = 0, j = 0, s = 0;
    while(ccw(conpep.back(), cake[i], conpep[0]) == 1 && conpep.size() > 1) ((--i) += n) %= n;
    while(ccw(conpep.back(), cake[i], conpep[0]) != 1 && conpep.size() > 1) (++i) %= n;
    j = (i + 1) % n;
    ans = 0;
    lp(cur, 0, conpep.size() - 1){ 
        ll ncur = (cur + 1) % conpep.size();
        while(ccw(cake[i], conpep[cur], conpep[ncur]) == 1 || conpep.size() == 1){
            bool ok = 1;
            while(ccw(cake[(j + 1) % n], conpep[cur], cake[i]) == 1){
                s += valccw(cake[(j + 1) % n], cake[i], cake[j]);
                (++j) %= n;
            }
            ans = max(ans, s);
            s -= valccw(cake[i], cake[(i + 1) % n], cake[j]);
            (++i) %= n;
            if(i == j) (++j) %= n;
            if(cnt[i]) break;
            cnt[i] = 1;
        }
        ans = max(ans, s);
    }
    cout << ans;
}

Compilation message

sir.cpp: In function 'void find_con()':
sir.cpp:7:37: 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]
    7 | #define lp(a, b, c) for(ll a = b; a <= c; ++a)
......
   66 |     lp(i, 1, pep.size() - 1){
      |        ~~~~~~~~~~~~~~~~~~~~          
sir.cpp:66:5: note: in expansion of macro 'lp'
   66 |     lp(i, 1, pep.size() - 1){
      |     ^~
sir.cpp:67:14: 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]
   67 |         if(i == pep.size() - 1 || ccw(pep[0], pep[i], pep.back()) <= 0){
      |            ~~^~~~~~~~~~~~~~~~~
sir.cpp:73:14: 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]
   73 |         if(i == pep.size() - 1 || ccw(pep[0], pep[i], pep.back()) >= 0){
      |            ~~^~~~~~~~~~~~~~~~~
sir.cpp:7:37: 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]
    7 | #define lp(a, b, c) for(ll a = b; a <= c; ++a)
......
   80 |     lp(i, 0, down.size() - 1) conpep.push_back(down[i]);
      |        ~~~~~~~~~~~~~~~~~~~~~         
sir.cpp:80:5: note: in expansion of macro 'lp'
   80 |     lp(i, 0, down.size() - 1) conpep.push_back(down[i]);
      |     ^~
sir.cpp: In function 'int main()':
sir.cpp:7:37: 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]
    7 | #define lp(a, b, c) for(ll a = b; a <= c; ++a)
......
  107 |     lp(cur, 0, conpep.size() - 1){
      |        ~~~~~~~~~~~~~~~~~~~~~~~~~     
sir.cpp:107:5: note: in expansion of macro 'lp'
  107 |     lp(cur, 0, conpep.size() - 1){
      |     ^~
sir.cpp:110:18: warning: unused variable 'ok' [-Wunused-variable]
  110 |             bool ok = 1;
      |                  ^~
sir.cpp: In function 'void OF()':
sir.cpp:38:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |         freopen(Fname".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
sir.cpp:39:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |         freopen(Fname".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
sir.cpp:41:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |         freopen(Fname".in", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sir.cpp:42:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |         freopen(Fname".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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

39.0 / 39.0

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

Subtask #3

49.0 / 49.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	151 ms	15160 KB	Output is correct
2	Correct	135 ms	12008 KB	Output is correct
3	Correct	135 ms	15668 KB	Output is correct
4	Correct	33 ms	4464 KB	Output is correct
5	Correct	104 ms	13240 KB	Output is correct
6	Correct	112 ms	11436 KB	Output is correct