oj.uz

Submission #537632

# Submission time Handle Problem Language Result Execution time Memory
537632 2022-03-15T10:18:07 Z zaneyu Planine (COCI21_planine) C++14
30 / 110
 26 ms 4076 KB 
/*input

*/
#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);
}
bool cmp(pdd a,pdd b){
    return a.s<b.s;
}
pii arr[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),cmp);
    ld cur=vv[0].s;
    int ans=1;
    for(auto x:vv){
        //cout<<x.s<<' '<<x.f<<'\n';
        if(x.f>cur) ++ans,cur=x.s;
    }
    cout<<ans;
    
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 852 KB Output is correct
2 Correct 3 ms 852 KB Output is correct
3 Correct 3 ms 852 KB Output is correct
4 Incorrect 26 ms 4076 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 212 KB Output is correct

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 852 KB Output is correct
2 Correct 3 ms 852 KB Output is correct
3 Correct 3 ms 852 KB Output is correct
4 Incorrect 26 ms 4076 KB Output isn't correct
5 Halted 0 ms 0 KB -