#include <bits/stdc++.h>
using namespace std;
#define sf scanf
#define pf printf
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) x.begin(),x.end()
#define INF 1023456789
typedef long long ll;
typedef long double ld;
typedef pair<ld,ld> ii;
#define maxn 1000005
int n,h,x[maxn],y[maxn],px[maxn],py[maxn],nx[maxn],ny[maxn];
struct line{
ll x1,x2,y1,y2;
int cross(line &o){//where does this line intersect
ll x3=o.x1,x4=o.x2,y3=o.y1,y4=o.y2;
if((x1-x2)*(y3-y4)==(x3-x4)*(y1-y2))return 2;//parallel
ll num=(y3-y4)*(y1*(x1-x2)-x1*(y1-y2))-(y1-y2)*(y3*(x3-x4)-x3*(y3-y4));
ll den=(y3-y4)*(x1-x2)-(y1-y2)*(x3-x4);
if(num==h*den)return 0;//intersect exactly
if((den>0&&num<h*den)||(den<0&&num>h*den))return -1;//intersect below
if((den>0&&num>h*den)||(den<0&&num<h*den))return 1;//intersect above
}
bool cmp(line &o){
ll a=x2-x1,b=y2-y1,c=o.x2-o.x1,d=o.y2-o.y1;
if(x1<o.x1){
if(b*c>d*a)return true;//intersect below
if(cross(o)<=0)return false;
else return true;
}
else{
if(b*c<d*a)return false;//intersect below
if(cross(o)==-1)return true;
else return false;
}
}
};
struct valley{
line l1,l2;
};
vector<valley> r;
vector<int> hull;
int main(){
sf("%d%d",&n,&h);
for(int i=1;i<=n;++i)sf("%d%d",&x[i],&y[i]);
x[0]=-1e6-1;y[0]=-INF;
hull.pb(0);
for(int i=1;i<=n;++i){
while(sz(hull)>=2){
int a=hull[sz(hull)-2],b=hull.back();
int x1=x[a],y1=y[a],x2=x[b],y2=y[b],x3=x[i],y3=y[i];
if((y2-y1)*(x3-x2)<=(y3-y2)*(x2-x1))hull.pop_back();
else break;
}
int a=hull.back();
px[i]=x[a],py[i]=y[a];
hull.push_back(i);
}
while(!hull.empty())hull.pop_back();
x[n+1]=1e6+1;y[n+1]=-INF;
hull.pb(n+1);
for(int i=n;i>=1;--i){
while(sz(hull)>=2){
int a=hull[sz(hull)-2],b=hull.back();
int x1=x[a],y1=y[a],x2=x[b],y2=y[b],x3=x[i],y3=y[i];
if((y1-y2)*(x2-x3)>=(y2-y3)*(x1-x2))hull.pop_back();
else break;
}
int a=hull.back();
nx[i]=x[a],ny[i]=y[a];
hull.push_back(i);
}
for(int i=3;i<n;i+=2){
line l1={x[i],px[i],y[i],py[i]};
line l2={x[i],nx[i],y[i],ny[i]};
r.pb({l1,l2});
}
sort(all(r),[](valley &a,valley &b){
return a.l2.cmp(b.l2);
});
int ans=0;
line pv=r[0].l1;
pv.x1-=1;pv.x2-=1;
for(int i=0;i<sz(r);++i){
if(pv.cross(r[i].l1)>=1){
++ans;pv=r[i].l2;
}
}
pf("%d\n",ans);
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:54:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
54 | sf("%d%d",&n,&h);
| ^
Main.cpp:55:25: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
55 | for(int i=1;i<=n;++i)sf("%d%d",&x[i],&y[i]);
| ^
Main.cpp: In member function 'int line::cross(line&)':
Main.cpp:30:2: warning: control reaches end of non-void function [-Wreturn-type]
30 | }
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
1232 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
1232 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
468 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
468 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
1232 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
1232 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
