제출 #537618

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
537618		zaneyu	Planine (COCI21_planine)	C++14	30 / 110	24 ms	4132 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<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);
}
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<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});
            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){
            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));
    ld cur=-INF;
    int ans=0;
    for(auto x:vv){
        if(x.f>cur) ++ans,cur=x.s;
        else MNTO(cur,x.s);
    }
    cout<<ans<<'\n';
}

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