Submission #370954

#	Time	Username	Problem	Language	Result	Execution time	Memory
370954		neki	Planine (COCI21_planine)	C++14	110 / 110	881 ms	91096 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

ll vecpro(par s, par p1, par p2){
    p1.fi-=s.fi;p1.se-=s.se;
    p2.fi-=s.fi;p2.se-=s.se;
    return p1.fi * p2.se - p2.fi * p1.se;
}
 
par inter(par p1, par p2, ll h){return make_pair(((h-p1.se) * (p2.fi - p1.fi) + p1.fi * (p2.se - p1.se)) , (p2.se - p1.se)) ;}
 
vc<par> gt(vc<par> a, ll h ){
    ll n=a.size();
    vc<par> st; 
    vc<par> 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));
        //cout << st.back().fi<<" "<<st.back().se<<" "<<a[i].fi<<" "<<a[i].se <<" "<<inter(st.back(), a[i], h)<<endl;
    }
    return ret;
}

ll qcmp(par a, par b){return a.fi * b.se < a.se * b.fi;}
ll cmp(pair<par, par> a, pair<par, par> b){
    return qcmp(a.fi, b.fi);
}

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<par> a=gt(poi, h);
    fore(v, a) if(v.se<0) v.fi*=-1, v.se*=-1;
    
    reverse(all(poi));
    fore(v, poi) v.fi=-v.fi;
    vc<par> b=gt(poi, h);
    fore(v, b) v.fi=-v.fi;
    fore(v, b) if(v.se<0) v.fi*=-1, v.se*=-1;
    reverse(all(b));
    
    n=a.size();
    vc<pair<par, par>> ints;
    loop(i, 0, n)  ints.ps(make_pair(a[i], b[i]));
    
    sort(all(ints), cmp);
    
    //loop(i, 0, n) cout << ints[i].fi << " "<< ints[i].se<<endl;
    
    par cur=make_pair(llmax, -1); ll ans=0;
    pool(i, n, 0){
        if(cur.fi==llmax or qcmp(ints[i].se, cur)) ans++, cur=ints[i].fi;
    }
    cout << ans<<endl;
}

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