Submission #537605

#	Time	Username	Problem	Language	Result	Execution time	Memory
537605		zaneyu	Planine (COCI21_planine)	C++14	0 / 110	23 ms	4416 KiB

Main

/*input
9 5
-5 2
-4 3
-2 1
0 4
2 2
3 3
4 1
5 2
6 1
*/
#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<int,int>
#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;
ld triangle(pdd o,pdd a,pdd b){
    if(a.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);
}
pii arr[maxn];
pdd ans[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<pdd> v;
    v.pb({-1e6-1,h});
    REP1(i,n-2){
        if(i%2){
            while(sz(v)>=2 and triangle(v[sz(v)-2],v[sz(v)-1],arr[i])>0){
                v.pop_back();
            }
            v.pb(arr[i]);
        }
        else{
            vv.pb({-INF,INF});
            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;
            
        }
    }
    REP(i,n) arr[i].f*=-1;
    v.clear();
    v.pb({-1e6-1,h});
    for(int i=n-2;i>=1;i--){
        if(i%2){
            while(sz(v)>=2 and triangle(v[sz(v)-2],v[sz(v)-1],arr[i])>0){
                v.pop_back();
            }
            v.pb(arr[i]);
        }
        else{
            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;
        }
    }
    sort(ALL(vv));
    ld cur=-INF-1;
    int ans=0;
    for(auto x:vv){
        //cout<<x.f<<' '<<x.s<<'\n';
        if(x.f>cur) ++ans,cur=x.s;
        else MNTO(cur,x.s);
    }
    cout<<ans<<'\n';
}

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