This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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;
};
vector <frac> L(n / 2), R(n / 2);
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();
int a = y[j] - y[i], b = x[j] - x[i];
L[i / 2 - 1] = frac((h - y[i]) * b + a * x[i], a);
} 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();
int a = y[j] - y[i], b = x[j] - x[i];
R[i / 2 - 1] = frac((h - y[i]) * b + a * x[i], a);
} dq.push_front(i);
}
int ans = 1, N = 1e7;
for ( int i = 0; i < n / 2; i++ ){
if ( !L[i].b ){
L[i] = {-N, 1};
}
if ( !R[i].b ){
R[i] = {N, 1};
}
}
cout << (n > 3);
return 0;
frac lst = R[0];
for ( int i = 1; i < n / 2; i++ ){
if ( L[i] <= lst ){
if ( R[i] <= lst ){
lst = R[i];
}
} else{
ans++;
lst = R[i];
}
}
cout << ans;
cout << '\n';
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |