Submission #386516

#	Time	Username	Problem	Language	Result	Execution time	Memory
386516		phathnv	Planine (COCI21_planine)	C++11	0 / 110	22 ms	16492 KiB

Main

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N = 1e6 + 7;

struct Fraction{
    ll p, q;
    Fraction(ll _p = 0, ll _q = 1){
        p = _p;
        q = _q;
        assert(q != 0);
        if (q < 0){
            p = -p;
            q = -q;
        }
        ll g = abs(__gcd(p, q));
        p /= g;
        q /= g;
    }
    bool operator == (const Fraction &oth) const {
        return (p == oth.p && q == oth.q);
    }
    bool operator < (const Fraction &oth) const {
        return ((long double) p * oth.q < (long double) oth.p * q);
    }
    bool operator <= (const Fraction &oth) const {
        return (oth == (*this) || (*this) < oth);
    }
};

struct Point{
    int x, y;
    Point(int _x = 0, int _y = 0){
        x = _x;
        y = _y;
    }
    Point operator - (const Point &oth) const {
        return Point(x - oth.x, y - oth.y);
    }
    ll operator * (const Point &oth) const {
        return (ll) x * oth.y - (ll) y * oth.x;
    }
};

struct Line{
    ll a, b, c;
    Line(ll _a, ll _b, ll _c){
        a = _a;
        b = _b;
        c = _c;
    }
    Line(const Point &A, const Point &B){
        a = A.y - B.y;
        b = B.x - A.x;
        c = (ll) A.x * B.y - (ll) A.y * B.x;
    }
};

int n, h;
Point p[N];

int findOrientation(const Point &A, const Point &B, const Point &C){
    ll x = (B - A) * (C - B);
    if (x < 0)
        return -1;
    else if (x == 0)
        return 0;
    else
        return 1;
}

Fraction findXCoor(const Line &d1, const Line &d2){
    ll D = d1.a * d2.b - d2.a * d1.b;
    ll Dx = -d1.c * d2.b + d2.c * d1.b;
    assert(D != 0);
    return Fraction(Dx, D);
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    freopen("inp.txt", "r", stdin);

    cin >> n >> h;
    for(int i = 1; i <= n; i++)
        cin >> p[i].x >> p[i].y;

    Line d(0, 1, -h);
    vector<pair<Fraction, Fraction>> segments(n / 2 - 1);
    vector<Point> cvh;
    for(int i = 1; i <= n; i++){
        while (cvh.size() > 1 && findOrientation(cvh[cvh.size() - 2], cvh[cvh.size() - 1], p[i]) > -1)
            cvh.pop_back();
        if (i % 2 && 3 <= i && i <= n - 2)
            segments[i / 2 - 1].first = findXCoor(Line(p[i], cvh.back()), d);
        cvh.push_back(p[i]);
    }
    for(int i = n; i >= 1; i--){
        while (cvh.size() > 1 && findOrientation(cvh[cvh.size() - 2], cvh[cvh.size() - 1], p[i]) < 1)
            cvh.pop_back();
        if (i % 2 && 3 <= i && i <= n - 2)
            segments[i / 2 - 1].second = findXCoor(Line(p[i], cvh.back()), d);
        cvh.push_back(p[i]);
    }
    vector<int> ok(segments.size());
    int answer = 0;
    while(true){
        Fraction minX = Fraction(1e18, 1);
        bool stop = 1;
        for(int i = 0; i < (int) segments.size(); i++)
            if (!ok[i]){
                stop = 0;
                minX = min(minX, segments[i].second);
            }
        if (stop)
            break;
        answer++;
        for(int i = 0; i < (int) segments.size(); i++)
            if (segments[i].first <= minX && minX <= segments[i].second)
                ok[i] = 1;
    }

    cout << answer;
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:85:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   85 |     freopen("inp.txt", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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