Submission #537634

#	Time	Username	Problem	Language	Result	Execution time	Memory
537634		zaneyu	Planine (COCI21_planine)	C++14	20 / 110	304 ms	32624 KiB

Main

/*input

*/
#include<bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
#define MNTO(x,y) x=min(x,y)
#define MXTO(x,y) x=max(x,y)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define ll long long
#define ld long double
#define sz(x) (int)x.size()
#define pii pair<ll,ll>
#define pdd pair<ld,ld>
#define f first
#define s second
#define pb push_back
#define ALL(x) x.begin(),x.end()
const int INF=0x3f3f3f3f;
const int maxn=1e6+5;
ll triangle(pii o,pii a,pii b){
    if(o.f==-1e6-1) return a.s<=b.s;
    return (a.f-o.f)*(b.s-o.s)-(b.f-o.f)*(a.s-o.s);
}
bool cmp(pdd a,pdd b){
    return a.s<b.s;
}
const ld eps=1e-9;
pii arr[maxn];
int main(){
    ios::sync_with_stdio(false),cin.tie(0);
    int n,h;
    cin>>n>>h;
    vector<pdd> vv;
    REP(i,n) cin>>arr[i].f>>arr[i].s;
    vector<pii> v;
    v.pb({-1e6-1,h});
    REP1(i,n-2){
        while(sz(v)>=2 and triangle(v[sz(v)-2],v[sz(v)-1],arr[i])>0){
            v.pop_back();
        }
        if(i%2==0){
            vv.pb({0,0});
            assert(v.back()==arr[i-1]);
            ld m=1.0*(v.back().s-arr[i].s)/(v.back().f-arr[i].f);
            ld c=arr[i].s-m*arr[i].f;
            vv[sz(vv)-1].f=(h-c)/m;
        }
        v.pb(arr[i]);
    }
    REP(i,n) arr[i].f*=-1;
    v.clear();
    v.pb({-1e6-1,h});
    for(int i=n-2;i>=1;i--){
        while(sz(v)>=2 and triangle(v[sz(v)-2],v[sz(v)-1],arr[i])>0){
            v.pop_back();
        }
        if(i%2==0){
            assert(v.back()==arr[i+1]);
            ld m=1.0*(v.back().s-arr[i].s)/(v.back().f-arr[i].f);
            ld c=arr[i].s-m*arr[i].f;
            ld z=(h-c)/m;
            vv[i/2-1].s=-z;
        }
        v.pb(arr[i]);
    }
    sort(ALL(vv),cmp);
    ld cur=vv[0].s;
    int ans=1;
    for(auto x:vv){
        //cout<<x.s<<' '<<x.f<<'\n';
        if(x.f>cur+eps) ++ans,cur=x.s;
    }
    cout<<ans;
    
}

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