Submission #516107

#	Time	Username	Problem	Language	Result	Execution time	Memory
516107		KoD	Planine (COCI21_planine)	C++17	110 / 110	243 ms	70176 KiB

Main

#include <bits/stdc++.h>

using std::vector;
using std::array;
using std::pair;
using std::tuple;

using i64 = std::int64_t;

struct Point {
    int x, y;
    Point(int x = 0, int y = 0) : x(x), y(y) {}
    friend Point operator-(const Point& p, const Point& q) {
        return Point(p.x - q.x, p.y - q.y);
    } 
    friend i64 cross(const Point& p, const Point& q) {
        return (i64)p.x * q.y - (i64)p.y * q.x;
    }
};

struct Frac {
    i64 x, y;
    Frac(i64 x = 0, i64 y = 1) : x(x), y(y) {}
    friend Frac operator+(const Frac& a, const Frac& b) {
        return Frac(a.x * b.y + b.x * a.y, a.y * b.y);
    }
    friend Frac operator-(const Frac& a, const Frac& b) {
        return Frac(a.x * b.y - b.x * a.y, a.y * b.y);    
    }
    friend Frac operator*(const Frac& a, const Frac& b) {
        return Frac(a.x * b.x, a.y * b.y);
    }
    friend bool operator<(const Frac& a, const Frac& b) {
        return a.x * b.y < b.x * a.y;
    }
};

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int N, H;
    std::cin >> N >> H;
    vector<Point> P(N);
    for (auto& [x, y] : P) {
        std::cin >> x >> y;
    }
    vector<Point> pts;
    vector<Frac> left(N), right(N);
    for (int i = 1; i < N - 1; ++i) {
        if (i % 2 == 1) {
            int n = pts.size();
            while (n >= 2) {
                if (cross(P[i] - pts[n - 1], pts[n - 2] - pts[n - 1]) >= 0) {
                    pts.pop_back();
                    n -= 1;
                } else {
                    break;
                }
            }
            pts.push_back(P[i]);
        } else {
            int ok = 0, ng = pts.size();
            while (ng - ok > 1) {
                const int md = (ok + ng) / 2;
                (cross(P[i] - pts[md], pts[md - 1] - pts[md]) < 0 ? ok : ng) = md;
            }
            left[i] = Frac(P[i].x) + Frac(pts[ok].x - P[i].x) * Frac(H - P[i].y, pts[ok].y - P[i].y);
        }
    }
    pts.clear();
    for (int i = N - 2; i >= 1; --i) {
        if (i % 2 == 1) {
            int n = pts.size();
            while (n >= 2) {
                if (cross(P[i] - pts[n - 1], pts[n - 2] - pts[n - 1]) <= 0) {
                    pts.pop_back();
                    n -= 1;
                } else {
                    break;
                }
            }
            pts.push_back(P[i]);
        } else {
            int ok = 0, ng = pts.size();
            while (ng - ok > 1) {
                const int md = (ok + ng) / 2;
                (cross(P[i] - pts[md], pts[md - 1] - pts[md]) > 0 ? ok : ng) = md;
            }
            right[i] = Frac(P[i].x) + Frac(pts[ok].x - P[i].x) * Frac(H - P[i].y, pts[ok].y - P[i].y);
        }
    }
    vector<pair<Frac, Frac>> interval;
    for (int i = 2; i < N - 2; i += 2) {
        interval.emplace_back(right[i], left[i]);
    }
    std::sort(interval.begin(), interval.end());
    Frac last(-2000000000000);
    int ans = 0;
    for (const auto& [r, l] : interval) {
        if (last < l) {
            ans += 1;
            last = r;
        }
    }
    std::cout << ans << '\n';
    return 0;
}

• Subtask 1: 20 / 20
• Subtask 2: 30 / 30
• Subtask 3: 60 / 60