#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 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) || !cmp(L[i], last)){
//printf("setting new R\n");
last = R[i];
ct++;
}
}
printf("%d",ct);
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:34:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
34 | scanf("%d%lld",&n,&h);
| ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:38:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
38 | scanf("%lld%lld",&p[i].fi,&p[i].se);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
6 ms |
1620 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
5 ms |
724 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
6 ms |
1620 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
