#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define ar array
#define pb push_back
#define ln '\n'
#define int long long
using i64 = long long;
template <class F, class _S>
bool chmin(F &u, const _S &v){
bool flag = false;
if ( u > v ){
u = v; flag |= true;
}
return flag;
}
template <class F, class _S>
bool chmax(F &u, const _S &v){
bool flag = false;
if ( u < v ){
u = v; flag |= true;
}
return flag;
}
struct frac{
int a, b;
frac(int a = 0, int b = 1) : a(a), b(b) {}
bool operator <=(const frac &t){
return a * t.b <= b * t.a;
}
};
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, h; cin >> n >> h;
vector <int> x(n), y(n);
for ( int i = 0; i < n; i++ ){
cin >> x[i] >> y[i];
}
auto ok = [&](int i, int j, int k, int s){
return (x[j] - x[i]) * (y[k] - y[i]) * s >= (x[k] - x[i]) * (y[j] - y[i]) * s;
};
using ld = long double;
const ld inf = 1e18, eps = 1e-8;
vector <ld> L(n / 2 - 1), R(n / 2 - 1);
deque <int> dq;
dq.pb(0);
for ( int i = 1; i + 1 < n; i++ ){
while ( dq.size() > 1 && ok(dq[(int)dq.size() - 2], dq.back(), i, 1) ){
dq.pop_back();
}
if ( i % 2 == 0 ){
int j = dq.back();
ld a = y[j] - y[i], b = x[j] - x[i], p = (h - y[i]) * b + a * x[i], q = a;
L[i / 2 - 1] = !q ? -inf : p / q;
} dq.pb(i);
}
dq.clear();
dq.pb(n - 1);
for ( int i = n - 2; i > 0; i-- ){
while ( dq.size() > 1 && ok(dq[1], dq[0], i, -1) ){
dq.pop_front();
}
if ( i % 2 == 0 ){
int j = dq.front();
ld a = y[j] - y[i], b = x[j] - x[i], p = (h - y[i]) * b + a * x[i], q = a;
R[i / 2 - 1] = !q ? inf : p / q;
} dq.push_front(i);
}
int ans = 1;
ld lst = R[0];
for ( int i = 1; i < L.size(); i++ ){
if ( L[i] <= lst + eps ){
if ( R[i] <= lst + eps ){
lst = R[i];
}
} else{
ans++;
lst = R[i];
}
}
cout << ans;
cout << '\n';
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:82:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long double>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
82 | for ( int i = 1; i < L.size(); i++ ){
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
600 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
600 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
