Submission #370948

#	Time	Username	Problem	Language	Result	Execution time	Memory
370948		neki	Planine (COCI21_planine)	C++14	30 / 110	7 ms	1224 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=0;
 
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;
    
    ll cur=llmax, ans=0;
    pool(i, n, 0){
        if(ints[i].se<cur) ans++, cur=ints[i].fi;
    }
    cout << ans<<endl;
}

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