#include <bits/stdc++.h>
using namespace std;
#define int long long
vector<pair<int,int> > hull[2];
void add(int x, int y, int no){
while (hull[no].size()>1){
auto t1 = hull[no].back();
auto t2 = *----hull[no].end();
bool b = (y-t1.second)*(x-t2.first)>=(x-t1.first)*(y-t2.second);
if (no) b = !b;
if (b){
hull[no].pop_back();
}
else break;
}
hull[no].push_back({x,y});
}
pair<int,int> qu(int x, int y, int no){
if (hull[no].size()==1){
return hull[no][0];
}
int l = -1;
int r = hull[no].size()-1;
while (l+1<r){
int mid = (l+r)/2;
auto t1 = hull[no][mid+1];
auto t2 = hull[no][mid];
bool b = (y-t1.second)*(x-t2.first)>=(x-t1.first)*(y-t2.second);
if (no) b = !b;
if (b) r = mid;
else l = mid;
}
return hull[no][r];
}
struct frac{
int a, b;
frac(){}
frac(int _a, int _b){
a = _a; b = _b;
}
bool operator<(frac other){
return a*other.b<other.a*b;
}
bool operator<=(frac other){
return a*other.b<=other.a*b;
}
bool operator==(frac other){
return a*other.b==other.a*b;
}
};
int X[1000005];
int Y[1000005];
frac L[1000005];
frac R[1000005];
main(){
int n,h;
scanf("%lld%lld",&n,&h);
if (n==3) {
printf("0");
return 0;
}
for (int x = 0; x<n; x++){
scanf("%lld%lld",&X[x],&Y[x]);
}
for (int x = 0; x<n; x++){
if (x==0) continue;
if (x==n-1) continue;
if (x&1){
add(X[x],Y[x],0);
}
else{
auto res = qu(X[x],Y[x],0);
//printf("res: %lld %lld\n",res.first,res.second);
res = {X[x-1],Y[x-1]};
L[x] = frac(X[x]*(res.second-Y[x])-(h-Y[x])*(X[x]-res.first),res.second-Y[x]);
}
}
for (int x = n-2; x>0; x--){
if (x&1){
add(X[x],Y[x],1);
}
else{
auto res = qu(X[x],Y[x],1);
res = {X[x+1],Y[x+1]};
R[x] = frac(X[x]*(res.second-Y[x])+(h-Y[x])*(res.first-X[x]),res.second-Y[x]);
}
}
vector<pair<frac,frac> > intervals;
for (int x = 2; x<n-1; x+=2){
intervals.push_back({R[x],L[x]});
}
frac cur = intervals[0].first;
int ans = 1;
for (auto x : intervals){
//printf("interval %lld/%lld to %lld/%lld\n",x.first.a,x.first.b,x.second.a,x.second.b);
if (x.second<=cur) continue;
ans++;
cur = x.first;
}
printf("%lld",ans);
}
/*
9 7
-999 0
-998 4
-1 2
0 4
1 0
3 4
4 2
998 4
999 0
*/
Compilation message
Main.cpp:62:2: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
62 | main(){
| ^~~~
Main.cpp: In function 'int main()':
Main.cpp:64:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
64 | scanf("%lld%lld",&n,&h);
| ~~~~~^~~~~~~~~~~~~~~~~~
Main.cpp:70:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
70 | scanf("%lld%lld",&X[x],&Y[x]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
1236 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
1236 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
