Submission #537564

#TimeUsernameProblemLanguageResultExecution timeMemory
537564zaneyuPlanine (COCI21_planine)C++14
0 / 110
2089 ms1332 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; pii arr[maxn]; int h; ld get(int a,int i){ ld m=1.0*(arr[a].s-arr[i].s)/(arr[a].f-arr[i].f); ld c=arr[i].s-m*arr[i].f; return (h-c)/m; } int main(){ ios::sync_with_stdio(false),cin.tie(0); int n; cin>>n>>h; REP(i,n) cin>>arr[i].f>>arr[i].s; vector<pdd> v; REP1(i,n-2){ if(i%2) continue; ld l=-INF,r=INF; REP(j,i){ if(j%2==0) continue; MXTO(l,get(j,i)); } for(int j=i+1;j<n;j+=2){ MNTO(r,get(j,i)); } v.pb({l,r}); } sort(ALL(v)); ld cur=-INF; int ans=0; for(auto x:v){ //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...