oj.uz

Submission #838244

# Submission time Handle Problem Language Result Execution time Memory
838244 2023-08-26T11:58:11 Z EntityPlantt Planine (COCI21_planine) C++17
110 / 110
 209 ms 82192 KB 
#include <cstdio>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
typedef long long ll;
struct frac {
    ll p, q;
    frac(const ll &_p = 0, const ll &_q = 0): p(_p), q(_q) {
        if (q < 0) {
            p = -p;
            q = -q;
        }
    }
    bool operator<(const frac &f) const {
        return p * f.q < q * f.p;
    }
    bool operator>(const frac &f) const {
        return f < *this;
    }
    double dbl() const {
        return double(p) / q;
    }
} l;
struct point {
    ll x, y;
    point(const ll &x = 0, const ll &y = 0): x(x), y(y) {}
};
frac direction(const point &A, const point &B) {
    return frac(A.y - B.y, A.x - B.x);
}
const ll mxn = 1000005;
ll n, h, i, c = 1;
point L[mxn], R[mxn], a[mxn];
vector <point> H;
pair <frac, frac> inte[mxn >> 1];
int main() {
    scanf("%lld%lld", &n, &h);
    if (n == 3) {
        printf("0");
        return 0;
    }
    for (i = 0; i < n; i++) {
        scanf("%lld%lld", &a[i].x, &a[i].y);
    }
    H.resize(1, *a);
    for (i = 1; i < n; i++) {
        while (H.size() > 1 && direction(H.rbegin()[1], a[i]) < direction(H.back(), a[i])) H.pop_back();
        L[i] = H.back();
        H.push_back(a[i]);
    }
    H.resize(1, a[n - 1]);
    for (i = n - 2; i >= 0; i--) {
        while (H.size() > 1 && direction(H.rbegin()[1], a[i]) > direction(H.back(), a[i])) H.pop_back();
        R[i] = H.back();
        H.push_back(a[i]);
    }
    for (i = 2; i < n - 1; i += 2) {
        /*inte[i].first = {L[i].x * (L[i].y - a[i].y) + (h - L[i].y) * (L[i].x - a[i].x), L[i].y - a[i].y};
        inte[i].second = {a[i].x * (a[i].y - R[i].y) + (h - a[i].y) * (a[i].x - R[i].x), a[i].y - R[i].y};*/
        inte[i / 2 - 1] = {frac(a[i].x * (L[i].y - a[i].y) + (h - a[i].y) * (L[i].x - a[i].x), L[i].y - a[i].y),
            frac(a[i].x * (R[i].y - a[i].y) + (h - a[i].y) * (R[i].x - a[i].x), R[i].y - a[i].y)};
    }
    sort(inte, inte + n / 2 - 1, [](auto &a, auto &b) { return a.second < b.second; });
    /*for (i = 0; i + 1 < n >> 1; i++) {
        printf("[(%lld, %lld), (%lld, %lld)]\n", inte[i].first.p, inte[i].first.q, inte[i].second.p, inte[i].second.q);
    }*/
    l = inte[0].second;
    for (i = 1; i + 1 < n >> 1; i++) {
        if (l < inte[i].first) {
            l = inte[i].second;
            c++;
        }
    }
    printf("%lld", c);
    return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:38:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |     scanf("%lld%lld", &n, &h);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~
Main.cpp:44:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |         scanf("%lld%lld", &a[i].x, &a[i].y);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 63000 KB Output is correct
2 Correct 26 ms 63040 KB Output is correct
3 Correct 26 ms 63016 KB Output is correct
4 Correct 40 ms 64028 KB Output is correct
5 Correct 39 ms 64052 KB Output is correct
6 Correct 40 ms 64052 KB Output is correct
7 Correct 173 ms 71188 KB Output is correct
8 Correct 180 ms 71248 KB Output is correct
9 Correct 194 ms 71188 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 62840 KB Output is correct
2 Correct 24 ms 62796 KB Output is correct
3 Correct 24 ms 62804 KB Output is correct
4 Correct 25 ms 62932 KB Output is correct
5 Correct 25 ms 62804 KB Output is correct
6 Correct 25 ms 62880 KB Output is correct
7 Correct 25 ms 62804 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 63000 KB Output is correct
2 Correct 26 ms 63040 KB Output is correct
3 Correct 26 ms 63016 KB Output is correct
4 Correct 40 ms 64028 KB Output is correct
5 Correct 39 ms 64052 KB Output is correct
6 Correct 40 ms 64052 KB Output is correct
7 Correct 173 ms 71188 KB Output is correct
8 Correct 180 ms 71248 KB Output is correct
9 Correct 194 ms 71188 KB Output is correct
10 Correct 25 ms 62840 KB Output is correct
11 Correct 24 ms 62796 KB Output is correct
12 Correct 24 ms 62804 KB Output is correct
13 Correct 25 ms 62932 KB Output is correct
14 Correct 25 ms 62804 KB Output is correct
15 Correct 25 ms 62880 KB Output is correct
16 Correct 25 ms 62804 KB Output is correct
17 Correct 185 ms 82192 KB Output is correct
18 Correct 181 ms 73808 KB Output is correct
19 Correct 40 ms 63972 KB Output is correct
20 Correct 184 ms 73000 KB Output is correct
21 Correct 40 ms 63816 KB Output is correct
22 Correct 199 ms 76592 KB Output is correct
23 Correct 25 ms 63036 KB Output is correct
24 Correct 177 ms 75840 KB Output is correct
25 Correct 41 ms 64028 KB Output is correct
26 Correct 209 ms 76956 KB Output is correct
27 Correct 33 ms 63596 KB Output is correct