#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;
}
};
bool cmp(pair<frac,frac> a, pair<frac,frac> b){
if (a.first==b.first) return a.second<b.second;
else return a.first<b.first;
}
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]});
}
sort(intervals.begin(),intervals.end(),cmp);
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:66:2: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
66 | main(){
| ^~~~
Main.cpp: In function 'int main()':
Main.cpp:68:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
68 | scanf("%lld%lld",&n,&h);
| ~~~~~^~~~~~~~~~~~~~~~~~
Main.cpp:74:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
74 | scanf("%lld%lld",&X[x],&Y[x]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
1236 KB |
Output is correct |
2 |
Correct |
3 ms |
1236 KB |
Output is correct |
3 |
Correct |
3 ms |
1236 KB |
Output is correct |
4 |
Correct |
24 ms |
7964 KB |
Output is correct |
5 |
Correct |
26 ms |
7984 KB |
Output is correct |
6 |
Correct |
28 ms |
8036 KB |
Output is correct |
7 |
Correct |
257 ms |
71572 KB |
Output is correct |
8 |
Correct |
280 ms |
71656 KB |
Output is correct |
9 |
Correct |
294 ms |
71616 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
468 KB |
Output is correct |
2 |
Correct |
1 ms |
468 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
468 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
488 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
1236 KB |
Output is correct |
2 |
Correct |
3 ms |
1236 KB |
Output is correct |
3 |
Correct |
3 ms |
1236 KB |
Output is correct |
4 |
Correct |
24 ms |
7964 KB |
Output is correct |
5 |
Correct |
26 ms |
7984 KB |
Output is correct |
6 |
Correct |
28 ms |
8036 KB |
Output is correct |
7 |
Correct |
257 ms |
71572 KB |
Output is correct |
8 |
Correct |
280 ms |
71656 KB |
Output is correct |
9 |
Correct |
294 ms |
71616 KB |
Output is correct |
10 |
Correct |
1 ms |
468 KB |
Output is correct |
11 |
Correct |
1 ms |
468 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
468 KB |
Output is correct |
14 |
Correct |
0 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
488 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
280 ms |
82616 KB |
Output is correct |
18 |
Correct |
264 ms |
74708 KB |
Output is correct |
19 |
Correct |
28 ms |
8364 KB |
Output is correct |
20 |
Correct |
266 ms |
73892 KB |
Output is correct |
21 |
Correct |
28 ms |
8148 KB |
Output is correct |
22 |
Correct |
289 ms |
77588 KB |
Output is correct |
23 |
Correct |
1 ms |
340 KB |
Output is correct |
24 |
Correct |
277 ms |
76748 KB |
Output is correct |
25 |
Correct |
29 ms |
8312 KB |
Output is correct |
26 |
Correct |
322 ms |
77832 KB |
Output is correct |
27 |
Correct |
13 ms |
4428 KB |
Output is correct |