oj.uz

Submission #899026

# Submission time Handle Problem Language Result Execution time Memory
899026 2024-01-05T11:05:56 Z WLZ Mobile (BOI12_mobile) C++17
100 / 100
 228 ms 104876 KB 
#include <bits/stdc++.h>
using namespace std;

#ifdef DEBUG
#include "debug.hpp"
#include "lib/geodeb.h"
#else
#define debug(...)
#define GD_INIT(...)
#define GD_POINT(...)
#define GD_LAYER(...)
#define GD_LINE(...)
#define GD_SEGMENT(...)
#endif

using ld = long double;
constexpr ld inf = numeric_limits<long double>::infinity();
constexpr ld eps = 1e-9;

// https://github.com/kth-competitive-programming/kactl/blob/main/content/geometry/Point.h
template<class T>
struct Point {
    typedef Point P;
    T x, y;
    explicit Point(T _x = 0, T _y = 0) : x(_x), y(_y) {}
    P operator+(P p) const { return P(x + p.x, y + p.y); }
    P operator-(P p) const { return P(x - p.x, y - p.y); }
    P operator/(T d) const { return P(x / d, y / d); }
    T dist2() const { return x*x + y*y; }
    ld dist() const { return sqrt((ld) dist2()); }
    P perp() const { return P(-y, x); }
};

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    GD_INIT("geodeb.html");

    int n; ld l; cin >> n >> l;
    vector< Point<int> > p1(n);
    for (int i = 0; i < n; i++) cin >> p1[i].x >> p1[i].y;
    int px = (int) -2e9, py = -2e9;
    vector< Point<ld> > p;
    for (auto &[x, y] : p1) {
        if (x == px) py = min(py, abs(y));
        else {
            if (px > (int) -2e9) p.emplace_back(px, py);
            px = x; py = abs(y);
        }
    }
    p.emplace_back(px, py);

    n = (int) p.size();
    GD_SEGMENT(0, 0, l, 0, "black bold");
    for (auto &[x, y] : p) GD_POINT(x, y, "black bold");

    vector<ld> ends = {-inf};
    vector< Point<ld> > st = {p[0]};

    for (int i = 1; i < n; i++) {
        GD_LAYER();
        GD_POINT(p[i].x, p[i].y, "red bold");

        while (true) {
            GD_LAYER();
            for (auto &e : ends) GD_POINT(clamp(e, 0.0l, l), 0, "red bold");

            auto q = st.back();
            GD_SEGMENT(p[i].x, p[i].y, q.x, q.y, "red bold");
            auto m = (p[i] + q) / 2;
            GD_POINT(m.x, m.y, "blue bold");
            auto tmp = (q - p[i]).perp() + m;
            GD_LINE(m.x, m.y, tmp.x, tmp.y, "black bold");
            ld k = -m.y / (q.x - p[i].x);
            ld x = m.x - k * (q.y - p[i].y);
            GD_POINT(x, 0, "blue bold");
            if (x < ends.back()) {
                st.pop_back(); ends.pop_back();
            } else {
                st.push_back(p[i]); ends.push_back(x);
                break;
            }
        }
        for (auto &e : ends) GD_POINT(clamp(e, 0.0l, l), 0, "red bold");
    }
    ends.push_back(inf);
    ld ans = 0.0;
    for (int i = 0; i < (int) st.size(); i++) {
        ld a = max(0.0l, ends[i]), b = min(l, ends[i + 1]);
        if (a < b) {
            ans = max(ans, (Point<ld>(a, 0) - st[i]).dist());
            ans = max(ans, (Point<ld>(b, 0) - st[i]).dist());
        }
    }
    cout << fixed << setprecision(4) << ans << '\n';

    return 0;
}

Compilation message

mobile.cpp: In function 'int main()':
mobile.cpp:54:16: warning: unused structured binding declaration [-Wunused-variable]
   54 |     for (auto &[x, y] : p) GD_POINT(x, y, "black bold");
      |                ^~~~~~
mobile.cpp:65:24: warning: unused variable 'e' [-Wunused-variable]
   65 |             for (auto &e : ends) GD_POINT(clamp(e, 0.0l, l), 0, "red bold");
      |                        ^
mobile.cpp:71:18: warning: variable 'tmp' set but not used [-Wunused-but-set-variable]
   71 |             auto tmp = (q - p[i]).perp() + m;
      |                  ^~~
mobile.cpp:83:20: warning: unused variable 'e' [-Wunused-variable]
   83 |         for (auto &e : ends) GD_POINT(clamp(e, 0.0l, l), 0, "red bold");
      |                    ^

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 456 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 860 KB Output is correct

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 856 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 2 ms 832 KB Output is correct

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 856 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 544 KB Output is correct
4 Correct 1 ms 860 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 860 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 2 ms 920 KB Output is correct
5 Correct 1 ms 540 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 5536 KB Output is correct
2 Correct 13 ms 4240 KB Output is correct
3 Correct 9 ms 3544 KB Output is correct
4 Correct 16 ms 6424 KB Output is correct
5 Correct 6 ms 1116 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1372 KB Output is correct
2 Correct 12 ms 3952 KB Output is correct
3 Correct 16 ms 8260 KB Output is correct
4 Correct 17 ms 7276 KB Output is correct
5 Correct 19 ms 8148 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 11984 KB Output is correct
2 Correct 13 ms 3288 KB Output is correct
3 Correct 17 ms 14152 KB Output is correct
4 Correct 24 ms 7756 KB Output is correct
5 Correct 13 ms 3288 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 3288 KB Output is correct
2 Correct 16 ms 4824 KB Output is correct
3 Correct 12 ms 3548 KB Output is correct
4 Correct 23 ms 7612 KB Output is correct
5 Correct 18 ms 8272 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 8144 KB Output is correct
2 Correct 15 ms 4820 KB Output is correct
3 Correct 12 ms 3548 KB Output is correct
4 Correct 23 ms 8400 KB Output is correct
5 Correct 21 ms 8412 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 53116 KB Output is correct
2 Correct 66 ms 4820 KB Output is correct
3 Correct 68 ms 4820 KB Output is correct
4 Correct 110 ms 22724 KB Output is correct
5 Correct 89 ms 28916 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 4820 KB Output is correct
2 Correct 87 ms 23944 KB Output is correct
3 Correct 67 ms 19960 KB Output is correct
4 Correct 116 ms 31936 KB Output is correct
5 Correct 93 ms 28420 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 77484 KB Output is correct
2 Correct 78 ms 5456 KB Output is correct
3 Correct 81 ms 14224 KB Output is correct
4 Correct 132 ms 50876 KB Output is correct
5 Correct 100 ms 30856 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 5460 KB Output is correct
2 Correct 105 ms 38332 KB Output is correct
3 Correct 78 ms 22784 KB Output is correct
4 Correct 132 ms 50624 KB Output is correct
5 Correct 113 ms 47996 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 83092 KB Output is correct
2 Correct 95 ms 6224 KB Output is correct
3 Correct 95 ms 16412 KB Output is correct
4 Correct 162 ms 52672 KB Output is correct
5 Correct 127 ms 32780 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 6208 KB Output is correct
2 Correct 124 ms 39072 KB Output is correct
3 Correct 90 ms 26256 KB Output is correct
4 Correct 157 ms 53952 KB Output is correct
5 Correct 130 ms 49600 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 90284 KB Output is correct
2 Correct 133 ms 6976 KB Output is correct
3 Correct 105 ms 18516 KB Output is correct
4 Correct 176 ms 56908 KB Output is correct
5 Correct 153 ms 35008 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 6972 KB Output is correct
2 Correct 144 ms 41396 KB Output is correct
3 Correct 110 ms 27848 KB Output is correct
4 Correct 176 ms 55708 KB Output is correct
5 Correct 145 ms 52668 KB Output is correct

Subtask #20
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 104876 KB Output is correct
2 Correct 129 ms 8528 KB Output is correct
3 Correct 133 ms 22988 KB Output is correct
4 Correct 228 ms 61628 KB Output is correct
5 Correct 165 ms 38604 KB Output is correct

Subtask #21
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 8528 KB Output is correct
2 Correct 181 ms 47408 KB Output is correct
3 Correct 137 ms 39872 KB Output is correct
4 Correct 215 ms 61876 KB Output is correct
5 Correct 202 ms 56756 KB Output is correct