#include <bits/stdc++.h>
//#include<ext/rope>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
//#pragma GCC target("avx2")
#define in(x) freopen(x, "r", stdin)
#define out(x) freopen(x, "w", stdout)
#define F first
#define S second
#define pb push_back
#define pri(x) cout << x << endl
#define sz(x) int(x.size())
#define el '\n'
#define _ << " " <<
#define pri(x) cout << x << endl
#define all(x) x.begin(), x.end()
using namespace std;
//using namespace __gnu_pbds;
//using namespace __gnu_cxx;
typedef long long ll;
typedef long double ld;
typedef short int si;
typedef unsigned long long ull;
//typedef tree <ll, null_type, less <ll> , rb_tree_tag, tree_order_statistics_node_update> ordered_set;
pair <int, int> operator -(pair <int, int> a, pair <int, int> b) {
return make_pair(a.F - b.F, a.S - b.S);
}
ll det(pair <int, int> a, pair <int, int> b) {
return a.F * 1ll * b.S - a.S * 1ll * b.F;
}
bool ccw(pair <int, int> a, pair <int, int> b, pair <int, int> c) {
return det(b - a, c - a) < 0;
}
vector <pair <int, int> > p;
int n, h;
vector <pair <int, int> > lft, rgt;
vector <pair <int, int> > build(int par) {
vector <pair <int, int> > ret;
vector <pair <pair <int, int>, int> > st;
for (int i = 1; i < n - 1; i++) {
while (sz(st) >= 2 && (ccw(st.rbegin()[1].F, st.rbegin()[0].F, p[i]) ^ par)) {
st.pop_back();
}
if (i % 2 == 0) {
ret.pb(st.back().F);
}
st.pb({p[i], i});
}
return ret;
}
struct fract {
ll a, b;
fract() {}
void go() {
ll gc = __gcd(a, b);
a /= gc; b /= gc;
}
fract(ll A, ll B) {a = A; b = B; go();}
};
bool operator <(fract &a, fract &b) {
return a.a * b.b < a.b * b.a;
}
bool operator ==(fract &a, fract &b) {
return a.a * b.b == a.b * b.a;
}
int main()
{
// cerr.precision(7);
// cerr << fixed;
ios_base::sync_with_stdio(0); istream::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// in("23.in");
// in("input.txt");
// out("output.txt");
// clock_t start = clock();
cin >> n >> h;
p.resize(n);
for (int i = 0; i < n; i++) {
cin >> p[i].F >> p[i].S;
}
lft = build(1);
reverse(all(p));
rgt = build(0);
reverse(all(p));
reverse(all(rgt));
assert(sz(rgt) == sz(lft));
vector <pair <fract, fract> > v;
for (int i = 0; i < sz(lft); i++) {
int j = 2 * (i + 1);
// ld k = ld(p[j].S - lft[i].S) / ld(p[j].F - lft[i].F);
// ld b = fract(p[j].S * (p[j].F - lft[i].F) - (p[j].S - lft[i].S) * p[j].F, p[j].F - lft[i].F);
fract lx = fract((h * (p[j].F - lft[i].F) - (p[j].S * (p[j].F - lft[i].F) - (p[j].S - lft[i].S) * p[j].F)) * (p[j].F - lft[i].F), (p[j].S - lft[i].S) * (p[j].F - lft[i].F));
// k = ld(p[j].S - rgt[i].S) / ld(p[j].F - rgt[i].F);
// b = p[j].S - k * p[j].F;
fract rx = fract((h * (p[j].F - rgt[i].F) - (p[j].S * (p[j].F - rgt[i].F) - (p[j].S - rgt[i].S) * p[j].F)) * (p[j].F - rgt[i].F), (p[j].S - rgt[i].S) * (p[j].F - rgt[i].F));
v.pb({lx, rx});
}
const ld eps = 1e-18;
sort(all(v), [&](pair <fract, fract> a, pair <fract, fract> b) {return (a.S < b.S || (a.S == b.S && a.F < b.F));});
int ans = 0;
fract R;
for (int i = 0; i < sz(v); i++) {
// cerr << v[i].F << " " << R << el;
if (!i || R < v[i].F) {
R = v[i].S;
ans++;
}
}
cout << ans;
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:116:14: warning: unused variable 'eps' [-Wunused-variable]
116 | const ld eps = 1e-18;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
844 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
844 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
