| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 537598 | maomao90 | Planine (COCI21_planine) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// 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];
bool used[MAXN];
int ans;
struct frac {
__int128 a, b;
frac(): a(0), b(1) {}
frac(ll _a): a(_a), b(1) {}
frac(ll _a, ll _b): a(_a), b(_b) {
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 {
return a == o.a && b == o.b;
}
bool operator<=(const frac &o) const {
return *this == o || *this < o;
}
};
struct Range {
frac l, r;
bool operator<(const Range &o) const {
return r < o.r;
}
};
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];
}
for (int i = 2; i < n - 1; i += 2) {
frac l = frac(x[i]) - frac((ll) (x[i] - x[i - 1]) * (h - y[i]), y[i - 1] - y[i]);
frac r = frac(x[i]) + frac((ll) (x[i + 1] - x[i]) * (h - y[i]), y[i + 1] - y[i]);
ranges.pb((Range) {l, r});
}
sort(ALL(ranges));
REP (i, 0, ranges.size()) {
if (used[i]) continue;
frac x = ranges[i].r;
ans++;
REP (j, i, ranges.size()) {
if (ranges[j].l <= x && x <= ranges[j].r) {
used[j] = 1;
}
}
}
cout << ans << '\n';
return 0;
}