oj.uz

답안 #537634

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
537634 2022-03-15T10:20:29 Z zaneyu Planine (COCI21_planine) C++14
20 / 110
 304 ms 32624 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;
}
const ld eps=1e-9;
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});
            assert(v.back()==arr[i-1]);
            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){
            assert(v.back()==arr[i+1]);
            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+eps) ++ans,cur=x.s;
    }
    cout<<ans;
    
}

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 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 Correct 24 ms 4076 KB Output is correct
5 Correct 29 ms 4012 KB Output is correct
6 Correct 31 ms 4084 KB Output is correct
7 Correct 282 ms 32424 KB Output is correct
8 Correct 276 ms 32436 KB Output is correct
9 Correct 304 ms 32624 KB Output is correct

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Runtime error 1 ms 468 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# 결과 실행 시간 메모리 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 Correct 24 ms 4076 KB Output is correct
5 Correct 29 ms 4012 KB Output is correct
6 Correct 31 ms 4084 KB Output is correct
7 Correct 282 ms 32424 KB Output is correct
8 Correct 276 ms 32436 KB Output is correct
9 Correct 304 ms 32624 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Runtime error 1 ms 468 KB Execution killed with signal 6
12 Halted 0 ms 0 KB -