Submission #537590

#TimeUsernameProblemLanguageResultExecution timeMemory
537590zaneyuPlanine (COCI21_planine)C++14
0 / 110
24 ms4596 KiB
/*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){ 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}); if(v.back().s>arr[i].s){ ld m=(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{ if(v.back().s>arr[i].s){ ld m=(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'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...