#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb emplace_back
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
typedef long long ll;
typedef pair<int,int> ii;
typedef pair<ii,ii> i4;
const int MOD=1000000007;
const int INF=1012345678;
const ll LLINF=1012345678012345678LL;
const double PI=3.1415926536;
//const double EPS=1e-14;
const double EPS=1e-10;
const int maxn=1000005;
int n,h;
int x[maxn],y[maxn];
double le[maxn];
pair<double,double> range[maxn]; // right, left
int num=0;
struct ch{
vector<ii> v;
void add(int i){ // add the point of index i
while(SZ(v)>=2){
ii a=v[SZ(v)-2],b=mp(x[i],y[i]);
double m=(double)(b.se-a.se)/(double)(b.fi-a.fi);
double c=(double)b.se-m*(double)(b.fi);
if(v.back().se<EPS+m*(double)(v.back().fi)+c)v.pop_back();
else break;
}
v.pb(x[i],y[i]);
}
double qry(){ // intersection of the most recent line with y=h
if(SZ(v)<2)return INF;
ii a=v[SZ(v)-2],b=v.back();
double m=(double)(b.se-a.se)/(double)(b.fi-a.fi);
double c=(double)b.se-m*(double)(b.fi);
return ((double)(h)-c)/m;
}
}fwd,bwd;
int main(){
scanf("%d%d",&n,&h);
for(int i=0;i<n;i++){
scanf("%d%d",&x[i],&y[i]);
}
for(int i=0;i<n-1;i++){
fwd.add(i);
if(i%2==0&&i>0)le[i]=fwd.qry();
}
for(int i=n-1;i>0;i--){
bwd.add(i);
if(i%2==0&&i<n-1){
range[num++]=mp(bwd.qry(),le[i]);
//printf("%f %f\n",range[num-1].fi,range[num-1].se);
}
}
sort(range,range+num);
double prv=-INF;
int ctr=0;
for(int i=0;i<num;i++){
if(prv+EPS>=range[i].se){
continue;
}
prv=range[i].fi;
ctr++;
}
printf("%d",ctr);
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:49:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
49 | scanf("%d%d",&n,&h);
| ~~~~~^~~~~~~~~~~~~~
Main.cpp:51:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
51 | scanf("%d%d",&x[i],&y[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
468 KB |
Output is correct |
2 |
Correct |
3 ms |
644 KB |
Output is correct |
3 |
Correct |
3 ms |
704 KB |
Output is correct |
4 |
Correct |
21 ms |
3660 KB |
Output is correct |
5 |
Correct |
24 ms |
3788 KB |
Output is correct |
6 |
Correct |
26 ms |
3980 KB |
Output is correct |
7 |
Correct |
240 ms |
33700 KB |
Output is correct |
8 |
Correct |
226 ms |
35768 KB |
Output is correct |
9 |
Correct |
263 ms |
37744 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
280 KB |
Output is correct |
2 |
Correct |
2 ms |
356 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
308 KB |
Output is correct |
6 |
Correct |
1 ms |
324 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
468 KB |
Output is correct |
2 |
Correct |
3 ms |
644 KB |
Output is correct |
3 |
Correct |
3 ms |
704 KB |
Output is correct |
4 |
Correct |
21 ms |
3660 KB |
Output is correct |
5 |
Correct |
24 ms |
3788 KB |
Output is correct |
6 |
Correct |
26 ms |
3980 KB |
Output is correct |
7 |
Correct |
240 ms |
33700 KB |
Output is correct |
8 |
Correct |
226 ms |
35768 KB |
Output is correct |
9 |
Correct |
263 ms |
37744 KB |
Output is correct |
10 |
Correct |
1 ms |
280 KB |
Output is correct |
11 |
Correct |
2 ms |
356 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
308 KB |
Output is correct |
15 |
Correct |
1 ms |
324 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
242 ms |
34772 KB |
Output is correct |
18 |
Correct |
275 ms |
34604 KB |
Output is correct |
19 |
Correct |
23 ms |
3660 KB |
Output is correct |
20 |
Correct |
237 ms |
33744 KB |
Output is correct |
21 |
Correct |
25 ms |
3660 KB |
Output is correct |
22 |
Correct |
259 ms |
37504 KB |
Output is correct |
23 |
Correct |
1 ms |
340 KB |
Output is correct |
24 |
Correct |
236 ms |
36784 KB |
Output is correct |
25 |
Correct |
26 ms |
3740 KB |
Output is correct |
26 |
Correct |
271 ms |
37708 KB |
Output is correct |
27 |
Correct |
12 ms |
1968 KB |
Output is correct |