// Hallelujah, praise the one who set me free
// Hallelujah, death has lost its grip on me
// You have broken every chain, There's salvation in your name
// Jesus Christ, my living hope
#include <bits/stdc++.h>
using namespace std;
template <class T>
inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;}
#define REP(i, s, e) for (int i = s; i < e; i++)
#define RREP(i, s, e) for (int i = s; i >= e; i--)
typedef long long ll;
typedef long double ld;
#define MP make_pair
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
#define MT make_tuple
typedef tuple<int, int, int> iii;
#define ALL(_a) _a.begin(), _a.end()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
#ifndef DEBUG
#define cerr if (0) cerr
#endif
#define INF 1000000005
#define LINF 1000000000000000005ll
#define MAXN 1000005
int n, h;
int x[MAXN], y[MAXN];
int ans;
struct frac {
ll a, b;
frac(): a(0), b(1) {}
frac(ll _a): a(_a), b(1) {}
frac(ll _a, ll _b): a(_a), b(_b) {
if (b == 0) {
a = LINF;
b = 1;
return;
}
ll g = __gcd(abs(a), abs(b));
a /= g;
b /= g;
if (b < 0) {
a *= -1;
b *= -1;
}
}
frac operator+(const frac &o) const {
return frac(a * o.b + b * o.a, b * o.b);
}
frac operator-(const frac &o) const {
return *this + (-o);
}
frac operator-() const {
return frac(-a, b);
}
bool operator<(const frac &o) const {
assert(b > 0 && o.b > 0);
return a * o.b < b * o.a;
}
bool operator>(const frac &o) const {
assert(b > 0 && o.b > 0);
return a * o.b > b * o.a;
}
bool operator==(const frac &o) const {
return a == o.a && b == o.b;
}
bool operator<=(const frac &o) const {
return *this == o || *this < o;
}
friend ostream& operator<<(ostream &os, const frac &o) {
return os << o.a << '/' << o.b;
}
};
struct Range {
frac l, r;
bool operator<(const Range &o) const {
return r < o.r;
}
};
frac l[MAXN], r[MAXN];
vector<Range> ranges;
int main() {
#ifndef DEBUG
ios::sync_with_stdio(0), cin.tie(0);
#endif
cin >> n >> h;
REP (i, 0, n) {
cin >> x[i] >> y[i];
}
REP (zz, 0, 2) {
vi pts;
REP (i, 1, n - 1) {
auto ori = [&] (int a, int b, int c) {
// b - a cross c - a
ll x1 = x[b] - x[a], y1 = y[b] - y[a],
x2 = x[c] - x[a], y2 = y[c] - y[a];
return x1 * y2 - x2 * y1;
};
while (pts.size() >= 2 && ori(pts[pts.size() - 2], pts[pts.size() - 1], i) > 0) {
pts.pop_back();
}
if (i % 2 == 0) {
int j = pts.back();
l[i] = frac(x[i]) - frac((ll) (x[i] - x[j]) * (h - y[i]), y[j] - y[i]);
}
pts.pb(i);
}
swap(l, r);
REP (i, 0, n) {
x[i] *= -1;
}
reverse(x, x + n);
reverse(y, y + n);
}
REP (i, 0, n) {
r[i] = -r[i];
}
reverse(r, r + n);
for (int i = 2; i < n - 1; i += 2) {
cerr << i << ": " << l[i] << ' ' << r[i] << '\n';
ranges.pb((Range) {l[i], r[i]});
}
sort(ALL(ranges));
frac x = frac(-1e12);
REP (i, 0, ranges.size()) {
if (x < ranges[i].l) {
x = ranges[i].r;
ans++;
}
}
cout << ans << '\n';
return 0;
}
/*
2: -6/1 2/3
4: -1/1 5/1
6: 2/1 8/1
*/
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:13:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Range>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
13 | #define REP(i, s, e) for (int i = s; i < e; i++)
......
141 | REP (i, 0, ranges.size()) {
| ~~~~~~~~~~~~~~~~~~~
Main.cpp:141:5: note: in expansion of macro 'REP'
141 | REP (i, 0, ranges.size()) {
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
32084 KB |
Output is correct |
| 2 |
Correct |
24 ms |
32064 KB |
Output is correct |
| 3 |
Correct |
26 ms |
32064 KB |
Output is correct |
| 4 |
Correct |
55 ms |
34660 KB |
Output is correct |
| 5 |
Correct |
65 ms |
34600 KB |
Output is correct |
| 6 |
Correct |
71 ms |
34632 KB |
Output is correct |
| 7 |
Correct |
325 ms |
56028 KB |
Output is correct |
| 8 |
Correct |
438 ms |
56000 KB |
Output is correct |
| 9 |
Correct |
505 ms |
55968 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
31720 KB |
Output is correct |
| 2 |
Correct |
24 ms |
31612 KB |
Output is correct |
| 3 |
Correct |
21 ms |
31584 KB |
Output is correct |
| 4 |
Correct |
27 ms |
31696 KB |
Output is correct |
| 5 |
Correct |
24 ms |
31576 KB |
Output is correct |
| 6 |
Correct |
24 ms |
31704 KB |
Output is correct |
| 7 |
Correct |
19 ms |
31584 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
32084 KB |
Output is correct |
| 2 |
Correct |
24 ms |
32064 KB |
Output is correct |
| 3 |
Correct |
26 ms |
32064 KB |
Output is correct |
| 4 |
Correct |
55 ms |
34660 KB |
Output is correct |
| 5 |
Correct |
65 ms |
34600 KB |
Output is correct |
| 6 |
Correct |
71 ms |
34632 KB |
Output is correct |
| 7 |
Correct |
325 ms |
56028 KB |
Output is correct |
| 8 |
Correct |
438 ms |
56000 KB |
Output is correct |
| 9 |
Correct |
505 ms |
55968 KB |
Output is correct |
| 10 |
Correct |
21 ms |
31720 KB |
Output is correct |
| 11 |
Correct |
24 ms |
31612 KB |
Output is correct |
| 12 |
Correct |
21 ms |
31584 KB |
Output is correct |
| 13 |
Correct |
27 ms |
31696 KB |
Output is correct |
| 14 |
Correct |
24 ms |
31576 KB |
Output is correct |
| 15 |
Correct |
24 ms |
31704 KB |
Output is correct |
| 16 |
Correct |
19 ms |
31584 KB |
Output is correct |
| 17 |
Correct |
381 ms |
56016 KB |
Output is correct |
| 18 |
Correct |
378 ms |
56004 KB |
Output is correct |
| 19 |
Correct |
57 ms |
34580 KB |
Output is correct |
| 20 |
Correct |
363 ms |
56288 KB |
Output is correct |
| 21 |
Correct |
52 ms |
34660 KB |
Output is correct |
| 22 |
Correct |
527 ms |
56008 KB |
Output is correct |
| 23 |
Correct |
26 ms |
31644 KB |
Output is correct |
| 24 |
Correct |
443 ms |
55988 KB |
Output is correct |
| 25 |
Correct |
56 ms |
34636 KB |
Output is correct |
| 26 |
Correct |
397 ms |
55992 KB |
Output is correct |
| 27 |
Correct |
44 ms |
33212 KB |
Output is correct |
