Submission #537512

#	Time	Username	Problem	Language	Result	Execution time	Memory
537512		dantoh000	Planine (COCI21_planine)	C++14	0 / 110	4 ms	852 KiB

Main

#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<ll, ll> ii;
int n;
ll h;
ii p[1000005];
int Lid[1000005], Rid[1000005];
ii L[1000005], R[1000005];
int ord[1000005];
ll cross(ii x, ii y){
    return x.fi*y.se - x.se*y.fi;
}
bool cw(int a, int b, int c){
    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(int a, int b){
    return cmp(R[a], R[b]);
}
int main(){
    scanf("%d%lld",&n,&h);
    p[0].fi = -1e13;
    p[0].se = h;
    for (int i = 1; i <= n; i++){
        scanf("%lld%lld",&p[i].fi,&p[i].se);
    }
    deque<int> dq;
    dq.push_back(0);
    dq.push_back(0);
    for (int i = 1; i <= n; i++){
        while (dq.size() > 2 && !cw(dq[dq.size()-2], dq[dq.size()-1], i)){
            dq.pop_back();
        }
        Lid[i] = dq.back();
        dq.push_back(i);
    }
    p[n+1].fi = 1e13;
    p[n+1].se = h;
    dq.clear();
    dq.push_back(n+1);
    dq.push_back(n+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 = 1; i <= n; i++){
        L[i] = extrapolate(i,Lid[i]);
        R[i] = extrapolate(i,Rid[i]);
        //printf("%lld %lld, %lld %lld\n",L[i].fi,L[i].se, R[i].fi, R[i].se);
    }
    iota(ord+1,ord+n+1, 1);
    sort(ord+1, ord+n+1, cmp2);
    ii last = ii(-1e15,1);
    int ct=  0;
    for (int j = 1; j <= n; j++){
        int i = ord[j];
        if (i%2 == 0 || i == 1 || i == n) continue;
        //printf("range %d: ",i);
        //printf("%lld %lld vs %lld %lld\n",L[i].fi,L[i].se, last.fi, last.se);
        if (last == ii(-1e15,1) || !cmp3(L[i], last)){
            //printf("setting new R\n");
            last = R[i];
            ct++;
        }
    }
    printf("%d",ct);

}

Compilation message (stderr)

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

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