Submission #661304

#	Time	Username	Problem	Language	Result	Execution time	Memory
661304		esomer	Planine (COCI21_planine)	C++17	110 / 110	633 ms	93676 KiB

Main

#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 / 20
• Subtask 2: 30 / 30
• Subtask 3: 60 / 60