oj.uz

Submission #1098024

# Submission time Handle Problem Language Result Execution time Memory
1098024 2024-10-08T20:00:01 Z 0x34c Mobile (BOI12_mobile) C++17
100 / 100
 546 ms 114728 KB 
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define endl '\n'
#define ld long double
#define pdd pair<ld, ld>

using namespace std;

int dist2(pii a, pii b)
{
    return (a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second);
}

ld dist(pii a, ld x)
{
    ld x1 = a.first, y = a.second;
    return sqrt((x1 - x) * (x1 - x) + y * y);
}

const int INF2 = 1e12;
const int INF = 1e9 + 1;
ld eps = 1e-4;

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

    int N, L;
    cin >> N >> L;

    vector<pii> inp(N);
    map<int, int> closest;
    for (int i = 0; i < N; i++)
    {
        int x, y;
        cin >> x >> y;

        inp[i] = {x, y};

        if (!closest.count(x))
            closest[x] = y;
        else
            closest[x] = (abs(closest[x]) > abs(y) ? y : closest[x]);
    }

    vector<pii> pts;
    for (pii p : closest)
        pts.push_back(p);

    N = pts.size();

    auto calc_bp = [&](int idx1, int idx2)
    {
        try
        {
            ld x1 = pts[idx1].first, y1 = pts[idx1].second;
            ld x2 = pts[idx2].first, y2 = pts[idx2].second;

            if (x1 - x2 == 0)
                return (ld)-1;
            return ((ld)0.5) * (x1 + x2 + (y1 * y1 - y2 * y2) / (x1 - x2));
        }
        catch (const std::exception &e)
        {
            return (ld)-1;
        }
    };

    stack<int> stk;
    stk.push(0);
    vector<ld> dists, bps;
    for (int i = 1; i < N; i++)
    {
        try
        {
            ld bp = calc_bp(stk.top(), i);
            bool emp = false;

            while (!bps.empty() && bps.back() >= bp)
            {
                bps.pop_back();
                stk.pop();
                dists.pop_back();
                if (stk.empty())
                    emp = true;
                else
                    bp = calc_bp(stk.top(), i);
            }

            if (!emp)
            {
                bps.push_back(bp);
                dists.push_back(dist(pts[i], bp));
            }
            stk.push(i);
        }
        catch (const std::exception &e)
        {
        }
    }

    ld mx_dist = 0;
    for (int i = 0; i < (bps.empty() ? 0 : bps.size()); i++)
    {
        if (bps[i] < 0 || bps[i] > L)
            continue;
        mx_dist = max(mx_dist, dists[i]);
    }

    ld mn_start = INF2, mn_end = INF2;
    for (int i = 0; i < N; i++)
    {
        mn_start = min(mn_start, dist(pts[i], (ld)0));
        mn_end = min(mn_end, dist(pts[i], (ld)L));
    }

    mx_dist = max({mx_dist, mn_start, mn_end});
    cout << setprecision(4) << fixed << mx_dist << endl;
}

Compilation message

mobile.cpp:21:18: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+12' to '2147483647' [-Woverflow]
   21 | const int INF2 = 1e12;
      |                  ^~~~
mobile.cpp: In function 'int main()':
mobile.cpp:105:23: warning: comparison of integer expressions of different signedness: 'int' and 'long unsigned int' [-Wsign-compare]
  105 |     for (int i = 0; i < (bps.empty() ? 0 : bps.size()); i++)
      |                     ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 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 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 #3
4.0 / 4.0

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

Subtask #4
4.0 / 4.0

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

Subtask #5
4.0 / 4.0

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

Subtask #6
5.0 / 5.0

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

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 5320 KB Output is correct
2 Correct 34 ms 4312 KB Output is correct
3 Correct 20 ms 3808 KB Output is correct
4 Correct 34 ms 5480 KB Output is correct
5 Correct 6 ms 860 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 1372 KB Output is correct
2 Correct 24 ms 3064 KB Output is correct
3 Correct 38 ms 5436 KB Output is correct
4 Correct 50 ms 5840 KB Output is correct
5 Correct 36 ms 6352 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 10308 KB Output is correct
2 Correct 30 ms 4048 KB Output is correct
3 Correct 33 ms 9676 KB Output is correct
4 Correct 44 ms 6856 KB Output is correct
5 Correct 25 ms 2204 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 3820 KB Output is correct
2 Correct 42 ms 3796 KB Output is correct
3 Correct 29 ms 2724 KB Output is correct
4 Correct 49 ms 6976 KB Output is correct
5 Correct 44 ms 6168 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 9928 KB Output is correct
2 Correct 42 ms 3880 KB Output is correct
3 Correct 32 ms 2724 KB Output is correct
4 Correct 48 ms 7044 KB Output is correct
5 Correct 48 ms 6044 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 249 ms 54888 KB Output is correct
2 Correct 136 ms 4764 KB Output is correct
3 Correct 127 ms 4732 KB Output is correct
4 Correct 277 ms 31856 KB Output is correct
5 Correct 253 ms 23668 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 4820 KB Output is correct
2 Correct 246 ms 34472 KB Output is correct
3 Correct 211 ms 14028 KB Output is correct
4 Correct 295 ms 31848 KB Output is correct
5 Correct 265 ms 29896 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 315 ms 74268 KB Output is correct
2 Correct 129 ms 5456 KB Output is correct
3 Correct 124 ms 5424 KB Output is correct
4 Correct 350 ms 41640 KB Output is correct
5 Correct 310 ms 23632 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 5440 KB Output is correct
2 Correct 302 ms 41152 KB Output is correct
3 Correct 244 ms 13252 KB Output is correct
4 Correct 344 ms 41412 KB Output is correct
5 Correct 338 ms 38200 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 362 ms 80444 KB Output is correct
2 Correct 140 ms 6228 KB Output is correct
3 Correct 143 ms 6228 KB Output is correct
4 Correct 423 ms 46880 KB Output is correct
5 Correct 339 ms 22620 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 6324 KB Output is correct
2 Correct 345 ms 47028 KB Output is correct
3 Correct 301 ms 18196 KB Output is correct
4 Correct 402 ms 47124 KB Output is correct
5 Correct 409 ms 42336 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 428 ms 87332 KB Output is correct
2 Correct 151 ms 6996 KB Output is correct
3 Correct 142 ms 6992 KB Output is correct
4 Correct 440 ms 52460 KB Output is correct
5 Correct 407 ms 34244 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 7000 KB Output is correct
2 Correct 388 ms 53164 KB Output is correct
3 Correct 335 ms 18624 KB Output is correct
4 Correct 426 ms 52392 KB Output is correct
5 Correct 409 ms 46440 KB Output is correct

Subtask #20
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 492 ms 114728 KB Output is correct
2 Correct 188 ms 23888 KB Output is correct
3 Correct 184 ms 23008 KB Output is correct
4 Correct 525 ms 82620 KB Output is correct
5 Correct 467 ms 46024 KB Output is correct

Subtask #21
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 8528 KB Output is correct
2 Correct 478 ms 67596 KB Output is correct
3 Correct 427 ms 23584 KB Output is correct
4 Correct 538 ms 63412 KB Output is correct
5 Correct 546 ms 55820 KB Output is correct