Submission #367867

#	Time	Username	Problem	Language	Result	Execution time	Memory
367867		neki	Planine (COCI21_planine)	C++14	0 / 110	8 ms	1116 KiB

Main

#include <bits/stdc++.h>
#define ll long long
#define loop(i, a, b) for(ll i=a;i<b;i++)
#define pool(i, a, b) for(ll i=a-1;i>=b;i--)
#define fore(i, a) for(auto&& i:a)
#define fi first
#define se second
#define ps(a) push_back(a)
#define pb(a) pop_back(a)
#define sc scanf
#define vc vector
#define lb lower_bound
#define ub upper_bound
#define all(a) a.begin(), a.end()
#define llmax LLONG_MAX/2
#define llmin -LLONG_MAX/2
using namespace std;
#define mn 500100
#define par pair<ll, ll>
#define ld long double
#define mod 1000000007

ld eps=1e-9;

ll vecpro(par s, par p1, par p2){
    p1.fi-=s.fi;
    p2.fi-=s.fi;
    p1.se-=s.se;
    p2.se-=s.se;
    return p1.fi * p2.se - p2.fi * p1.se;
}

ld inter(par p1, par p2, ll h){
    ld k=((ld)(p2.se - p1.se)) / (p2.fi - p1.fi);
    return ((ld)(h-p1.se + k * p1.fi))/k;
}

vc<ld> gt(vc<par> a, ll h ){
    ll n=a.size();
    vc<par> st; 
    vc<ld> ret;
    
    for(ll i=1;i<n;i+=2){
        while(st.size()>=2 and vecpro(st[st.size()-1],  st[st.size()-2], a[i-1])<=0) st.pop_back();
        st.ps(a[i-1]);
        while(st.size()>=2 and vecpro(st[st.size()-1],  st[st.size()-2], a[i])<=0) st.pop_back();
        ret.ps(inter(st.back(), a[i], h)-eps);
        //cout << st.back().fi<<" "<<st.back().se<<" "<<a[i].fi<<" "<<a[i].se <<" "<<inter(st.back(), a[i], h)<<endl;
    }
    return ret;
}

int main() {
    ll n, h;cin >> n>>h;
    vc<par> poi;
    loop(i, 0, n){
        ll x, y;cin >> x >> y;
        if(i!=0 and i!=n-1)poi.ps(make_pair(x, y));
    }
    
    vc<ld> a=gt(poi, h);
    
    reverse(all(poi));
    fore(v, poi) v.fi=-v.fi;
    vc<ld> b=gt(poi, h);
    fore(v, b) v=-v;
    reverse(all(b));
    
    n=a.size();
    vc<pair<ld, ld>> ints;
    loop(i, 0, n)  ints.ps(make_pair(a[i], b[i]));
    ints.ps(make_pair(llmax, llmax));
    
    sort(all(ints));
    
    //loop(i, 0, n) cout << ints[i].fi << " "<< ints[i].se<<endl;
    
    vc<ll> dp(n+1, 0);
    pool(i, n, 0){
        ll odg=upper_bound(all(ints), make_pair((ld)ints[i].se, (ld)llmax))-ints.begin();//?????????????????
        dp[i]=1+dp[odg];
    }
    cout << dp[0]<<endl;
}

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