Submission #537537

#	Time	Username	Problem	Language	Result	Execution time	Memory
537537		dantoh000	Planine (COCI21_planine)	C++14	110 / 110	353 ms	50792 KiB

Main

#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<ll, ll> ii;
typedef pair<ii, ii> i4;
int n;
ll h;
ii p[1000005];
int Lid[1000005], Rid[1000005];
int ord[1000005];
ll cross(ii x, ii y){
    return x.fi*y.se - x.se*y.fi;
}
bool ccw(int a, int b, int c){
    if (a == -1) return (p[b].se <= p[c].se);
    ii x = ii(p[b].fi - p[a].fi, p[b].se - p[a].se);
    ii y = ii(p[c].fi - p[b].fi, p[c].se - p[b].se);
    return cross(x,y) > 0ll;
}
bool cw(int a, int b, int c){
    if (a == -1) return (p[b].se <= p[c].se);
    ii x = ii(p[b].fi - p[a].fi, p[b].se - p[a].se);
    ii y = ii(p[c].fi - p[b].fi, p[c].se - p[b].se);
    return cross(x,y) < 0ll;
}
ii extrapolate(int a, int b){
    ll dy = p[b].se - p[a].se;
    ll dx = p[b].fi - p[a].fi;
    return ii(p[a].fi*dy + (h-p[a].se)*dx, dy);
}
bool cmp(ii a, ii b){
    //printf("comparing (%lld,%lld) and (%lld,%lld)\n",a.fi,a.se,b.fi,b.se);
    return a.fi*b.se < b.fi*a.se;
}
bool cmp3(ii a, ii b){
    //printf("comparing (%lld,%lld) and (%lld,%lld)\n",a.fi,a.se,b.fi,b.se);
    return  a.fi*b.se > b.fi*a.se;
}
bool cmp2(i4 a, i4 b){
    return cmp(a.se, b.se);
}

vector<pair<ii, ii> > v;
int main(){
    scanf("%d%lld",&n,&h);
    for (int i = 1; i <= n; i++){
        scanf("%lld%lld",&p[i].fi,&p[i].se);
    }
    deque<int> dq;
    dq.push_back(-1);
    for (int i = 1; i <= n; i++){
        while (dq.size() >= 2 && ccw(dq[dq.size()-2], dq[dq.size()-1], i)){
            dq.pop_back();
        }
        Lid[i] = dq.back();
        dq.push_back(i);
    }
    dq.clear();
    dq.push_back(-1);
    for (int i = n; i >= 1; i--){
        while (dq.size() >= 2 && cw(dq[dq.size()-2], dq[dq.size()-1], i)){
            dq.pop_back();
        }
        Rid[i] = dq.back();
        dq.push_back(i);
    }
    for (int i = 3; i < n; i+=2){
        //printf("point %d goes to %d, %d\n",i,Lid[i],Rid[i]);
        ii L = extrapolate(i,Lid[i]);
        ii R = extrapolate(i,Rid[i]);
        v.push_back({L,R});
        //printf("%lld %lld, %lld %lld\n",L[i].fi,L[i].se, R[i].fi, R[i].se);
    }
    sort(v.begin(), v.end(), cmp2);
    ii last = v[0].se;
    int ct = 1;
    for (auto x : v){
        //printf("%lld %lld vs %lld %lld\n",x.fi.fi,x.fi.se, last.fi, last.se);
        if (cmp3(x.fi, last)){
            //printf("setting new R\n");
            last = x.se;
            ct++;
        }
    }
    printf("%d",ct);

}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:47:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |     scanf("%d%lld",&n,&h);
      |     ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:49:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |         scanf("%lld%lld",&p[i].fi,&p[i].se);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 30 / 30
• Subtask 3: 60 / 60