Submission #373052

#TimeUsernameProblemLanguageResultExecution timeMemory
373052sam571128Planine (COCI21_planine)C++14
20 / 110
293 ms43632 KiB
#include <bits/stdc++.h> #define int long long #define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); using namespace std; const int N = 1e6+5; const double EPS = 1e-7; pair<double,double> seg[N]; int st[N], id[N]; int n, h; double findp(int x1, int y1, int x2, int y2){ assert(y1!=y2); return 1.0*(h-y1)*(x2-x1)/(y2-y1)+x1; } bool check(pair<double,double> a, pair<double,double> b, pair<double,double> c){ return (b.second-a.second)*(c.first-a.first) < (c.second-a.second)*(b.first-a.first); } signed main(){ fastio //freopen("input.in","r",stdin); cin >> n >> h; vector<pair<double,double>> v(1); for(int i = 1;i <= n;i++){ int x,y; cin >> x >> y; v.push_back({x,y}); } vector<int> st; for (int i = 1; i <= n; i++) { //dy/dx < dy<dx => (v[st.top()].second-v[i].second) while(st.size() > 2&&check(v[i],v[st[st.size()-1]],v[st[st.size()-2]])) st.pop_back(); if(i%2==1&&!st.empty()) seg[i].first = findp(v[i].first,v[i].second, v[i-1].first, v[i-1].second); st.push_back(i); } st.clear(); for(int i = n; i >= 1; i--) { while(st.size() > 2&&check(v[i],v[st[st.size()-1]],v[st[st.size()-2]])) st.pop_back(); if(i%2==1&&!st.empty()) seg[i].second = findp(v[i].first,v[i].second, v[i+1].first, v[i+1].second); st.push_back(i); } for(int i = 3;i <= n;i++){ id[i/2] = i; } sort(id+1,id+n/2,[&](int a, int b){ return seg[a].second < seg[b].second; }); double tmp = seg[id[1]].second; int ans = 1; for (int i = 1; i <= n / 2 - 1; ++i) { if (tmp >= seg[id[i]].first) continue; //cout << seg[i].first << " " << seg[i].second << "\n"; tmp = seg[id[i]].second; ++ans; } cout << ans << "\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...