oj.uz

Submission #1097989

# Submission time Handle Problem Language Result Execution time Memory
1097989 2024-10-08T18:21:45 Z 0x34c Mobile (BOI12_mobile) C++17
0 / 100
 1000 ms 121564 KB 
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define endl '\n'
#define int ll
#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)
{
    return sqrt((((ld)a.first) - x) * (((ld)a.first) - x) + (ld)(a.second * a.second));
}

const int INF = 1e9 + 1;
const int INF2 = 1e12;
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] = abs(y);
        else
            closest[x] = min(closest[x], abs(y));
    }

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

    N = pts.size();
    vector<ld> bp(N);
    for (int i = 0; i < N - 1; i++)
    {
        ld l = -INF, r = INF;
        while ((r - l) > eps)
        {
            ld m = l + (r - l) / 2;

            ld d1 = dist(pts[i], m), d2 = dist(pts[i + 1], m);
            if (abs(d1 - d2) <= eps)
            {
                bp[i] = m;
                break;
            }
            else if (d1 < d2)
                l = m;
            else
                r = m;
        }
    }

    ld mx_dist = 0;
    for (int i = 0; i < N - 1; i++)
    {
        if (bp[i] < 0 || bp[i] > L)
            continue;
        mx_dist = max(mx_dist, dist(pts[i], bp[i]));
    }

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

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

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 860 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 860 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 95 ms 8904 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 2904 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 10884 KB Output is correct
2 Incorrect 61 ms 7880 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #10
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 64 ms 7632 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 152 ms 13056 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 817 ms 59480 KB Output is correct
2 Correct 145 ms 16892 KB Output is correct
3 Correct 137 ms 16448 KB Output is correct
4 Incorrect 879 ms 64860 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #13
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 17368 KB Output is correct
2 Incorrect 714 ms 61304 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #14
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 937 ms 71356 KB Output is correct
2 Correct 155 ms 19784 KB Output is correct
3 Incorrect 158 ms 19024 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #15
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 20248 KB Output is correct
2 Incorrect 856 ms 73400 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #16
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1052 ms 83228 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #17
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 23376 KB Output is correct
2 Execution timed out 1002 ms 85684 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #18
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1059 ms 95164 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #19
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 216 ms 26452 KB Output is correct
2 Execution timed out 1055 ms 97604 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #20
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1037 ms 118656 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #21
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 243 ms 32848 KB Output is correct
2 Execution timed out 1066 ms 121564 KB Time limit exceeded
3 Halted 0 ms 0 KB -