Submission #898593

#	Time	Username	Problem	Language	Result	Execution time	Memory
898593		vjudge1	Planine (COCI21_planine)	C++17	110 / 110	498 ms	94468 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define ld long double
#define P complex<ld>
#define X real()
#define Y imag()
int main() {
    cin.sync_with_stdio(false);
    cin.tie(nullptr);
    int n, h;
    cin >> n >> h;
    vector<P> mount(n), ch;
    for(auto &i: mount) {
        ld a, b;
        cin >> a >> b;
        i={a,b};
    }
    vector<pair<ld,ld>> a(n,{-1e18,-1e18});
    for(int i = 1; i < n-1; i++) {
        while(ch.size()>1&&((mount[i]-ch.back())*conj(ch.back()-ch[ch.size()-2])).Y>=0)
            ch.pop_back();
        if(~i&1) {
            P p = mount[i]-ch.back();
            a[i].first=mount[i].X+(p.X/p.Y*(h-mount[i].Y));
        }
        ch.push_back(mount[i]);
    }
    ch.clear();
    for(int i = n-1; --i;) {
        while(ch.size()>1&&((mount[i]-ch.back())*conj(ch.back()-ch[ch.size()-2])).Y<=0)
            ch.pop_back();
        if(~i&1) {
            P p = ch.back()-mount[i];
            a[i].second=mount[i].X+(p.X/p.Y*(h-mount[i].Y));
        }
        ch.push_back(mount[i]);
    }
    vector<pair<ld,ld>> v;
    for(auto i: a)
        if(i.first!=-1e18)
            v.push_back(i);
    sort(v.begin(),v.end());
    int ans = 0;
    ld x = -1e18;
    for(auto i: v) {
        if(i.first-x>1e-10)
            ans++,x=i.second;
        else x=min(x,i.second);
    }
    cout << ans << '\n';
}

• Subtask 1: 20 / 20
• Subtask 2: 30 / 30
• Subtask 3: 60 / 60