oj.uz

Submission #386519

# Submission time Handle Problem Language Result Execution time Memory
386519 2021-04-06T17:44:21 Z phathnv Planine (COCI21_planine) C++11
110 / 110
 400 ms 38124 KB 
#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);

    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]);
    }
    sort(segments.begin(), segments.end(), [](const pair<Fraction, Fraction> &a, const pair<Fraction, Fraction> &b){
            return a.second < b.second;
        });
    int answer = 0;
    Fraction lastX = Fraction(-1e18, 1);
    for(auto p : segments)
        if (lastX < p.first){
            answer++;
            lastX = p.second;
        }
    cout << answer;
    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8300 KB Output is correct
2 Correct 9 ms 8300 KB Output is correct
3 Correct 9 ms 8300 KB Output is correct
4 Correct 32 ms 9708 KB Output is correct
5 Correct 40 ms 9708 KB Output is correct
6 Correct 40 ms 9708 KB Output is correct
7 Correct 280 ms 23788 KB Output is correct
8 Correct 328 ms 23788 KB Output is correct
9 Correct 390 ms 23788 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8172 KB Output is correct
2 Correct 6 ms 8172 KB Output is correct
3 Correct 6 ms 8172 KB Output is correct
4 Correct 7 ms 8172 KB Output is correct
5 Correct 6 ms 8172 KB Output is correct
6 Correct 6 ms 8172 KB Output is correct
7 Correct 6 ms 8172 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8300 KB Output is correct
2 Correct 9 ms 8300 KB Output is correct
3 Correct 9 ms 8300 KB Output is correct
4 Correct 32 ms 9708 KB Output is correct
5 Correct 40 ms 9708 KB Output is correct
6 Correct 40 ms 9708 KB Output is correct
7 Correct 280 ms 23788 KB Output is correct
8 Correct 328 ms 23788 KB Output is correct
9 Correct 390 ms 23788 KB Output is correct
10 Correct 6 ms 8172 KB Output is correct
11 Correct 6 ms 8172 KB Output is correct
12 Correct 6 ms 8172 KB Output is correct
13 Correct 7 ms 8172 KB Output is correct
14 Correct 6 ms 8172 KB Output is correct
15 Correct 6 ms 8172 KB Output is correct
16 Correct 6 ms 8172 KB Output is correct
17 Correct 310 ms 34828 KB Output is correct
18 Correct 316 ms 34688 KB Output is correct
19 Correct 35 ms 10860 KB Output is correct
20 Correct 359 ms 34028 KB Output is correct
21 Correct 36 ms 10732 KB Output is correct
22 Correct 400 ms 37740 KB Output is correct
23 Correct 6 ms 8172 KB Output is correct
24 Correct 346 ms 37020 KB Output is correct
25 Correct 37 ms 10860 KB Output is correct
26 Correct 357 ms 38124 KB Output is correct
27 Correct 23 ms 9452 KB Output is correct