oj.uz

Submission #661304

# Submission time Handle Problem Language Result Execution time Memory
661304 2022-11-25T12:40:40 Z esomer Planine (COCI21_planine) C++17
110 / 110
 633 ms 93676 KB 
#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define endl "\n"
#define ld long double
#define P complex<ld>

const int MOD = 998244353;

bool les(ld a, ld b){
    if(a < b && abs(a - b) > 1e-10) return true;
    else return false;
}

void solve(){
    int n; ld h; cin >> n >> h;
    vector<P> mnt(n);
    for(int i = 0; i < n; i++){
        ld x, y; cin >> x >> y;
        mnt[i] = {x, y};
    }
    vector<pair<ld, ld>> a(n, {-1e18, -1e18});
    vector<P> ch;
    for(int i = 1; i < n - 1; i++){
        bool good = 0;
        while(!good){
            if((int)ch.size() < 2){
                ch.push_back(mnt[i]);
                good = 1;
            }else{
                P p = ch[(int)ch.size() - 1] - ch[(int)ch.size() - 2];
                P p1 = mnt[i] - ch[(int)ch.size() - 1];
                if(p.real() * p1.imag() - p1.real() * p.imag() >= 0) ch.pop_back();
                else{
                    good = 1;
                    ch.push_back(mnt[i]);
                }
            }
        }
        if(i % 2 == 0){
            P p = ch[(int)ch.size() - 2];
            ld difhor = mnt[i].real() - p.real();
            ld difver = p.imag() - mnt[i].imag();
            ld hdif = h - mnt[i].imag();
            a[i].first = mnt[i].real() - ((difhor / difver) * hdif);
        }
    }
    ch.resize(0);
    for(int i = n - 2; i >= 1; i--){
        bool good = 0;
        while(!good){
            if((int)ch.size() < 2){
                ch.push_back(mnt[i]);
                good = 1;
            }else{
                P p = ch[(int)ch.size() - 1] - ch[(int)ch.size() - 2];
                P p1 = mnt[i] - ch[(int)ch.size() - 1];
                if(p.real() * p1.imag() - p1.real() * p.imag() <= 0) ch.pop_back();
                else{
                    good = 1;
                    ch.push_back(mnt[i]);
                }
            }
        }
        if(i % 2 == 0){
            P p = ch[(int)ch.size() - 2];
            ld difhor = p.real() - mnt[i].real();
            ld difver = p.imag() - mnt[i].imag();
            ld hdif = h - mnt[i].imag();
            a[i].second = mnt[i].real() + ((difhor / difver) * hdif);
        }
    }
    vector<pair<ld, ld>> v;
    for(auto p : a){
        if(p.first != -1e18) v.push_back(p);
    }
    n = v.size();
    sort(v.begin(), v.end());
    int curr = 0;
    ld right = -1e18;
    for(int i = 0; i < n; i++){
        if(les(right, v[i].first)){
            curr++;
            right = v[i].second;
        }else right = min(right, v[i].second);
    }
    cout << curr << endl;
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    //freopen("inpt.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);

    //int tt; cin >> tt;
    int tt = 1;
    for(int t = 1; t <= tt; t++){
        solve();
    }
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1368 KB Output is correct
2 Correct 7 ms 1368 KB Output is correct
3 Correct 6 ms 1492 KB Output is correct
4 Correct 51 ms 9800 KB Output is correct
5 Correct 56 ms 9968 KB Output is correct
6 Correct 60 ms 10044 KB Output is correct
7 Correct 511 ms 89468 KB Output is correct
8 Correct 559 ms 91580 KB Output is correct
9 Correct 585 ms 93260 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 2 ms 464 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 2 ms 460 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 1 ms 340 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1368 KB Output is correct
2 Correct 7 ms 1368 KB Output is correct
3 Correct 6 ms 1492 KB Output is correct
4 Correct 51 ms 9800 KB Output is correct
5 Correct 56 ms 9968 KB Output is correct
6 Correct 60 ms 10044 KB Output is correct
7 Correct 511 ms 89468 KB Output is correct
8 Correct 559 ms 91580 KB Output is correct
9 Correct 585 ms 93260 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 2 ms 464 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 2 ms 460 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 2 ms 468 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 540 ms 90480 KB Output is correct
18 Correct 555 ms 90408 KB Output is correct
19 Correct 57 ms 9852 KB Output is correct
20 Correct 542 ms 89596 KB Output is correct
21 Correct 60 ms 9776 KB Output is correct
22 Correct 586 ms 93436 KB Output is correct
23 Correct 0 ms 340 KB Output is correct
24 Correct 574 ms 92672 KB Output is correct
25 Correct 56 ms 9804 KB Output is correct
26 Correct 633 ms 93676 KB Output is correct
27 Correct 26 ms 5108 KB Output is correct