oj.uz

답안 #537804

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
537804 2022-03-15T14:52:25 Z maomao90 Planine (COCI21_planine) C++17
110 / 110
 527 ms 56288 KB 
// 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()) {
      |     ^~~

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 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

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 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

Subtask #3
60.0 / 60.0

# 결과 실행 시간 메모리 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