Submission #1095261

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1095261	2024-10-01T16:50:23 Z	buzdi	Mobile (BOI12_mobile)	C++17	100 / 100	339 ms	63060 KB

mobile

#include <iostream>
#include <algorithm>
#include <cassert>
#include <cmath>
#include <iomanip>
#include <vector>
#include <queue>
#include <map>
#include <set>
#define ll long long

using namespace std;

const int NMAX = 1e6;
const long double EPS = 1e-3;

struct Point {
    long double x, y;
    void read() {
        cin >> x >> y;
    }
}points[NMAX + 1];

int n, l, ind_st, i;
long double answer;
pair<int, long double> st[NMAX + 1];

long double Square(long double x) {
    return x * x;
}

long double Distance(Point p1, Point p2) {
    return sqrt(Square(p1.x - p2.x) + Square(p1.y - p2.y));
}

long double WhereBetter(Point p1, Point p2) {
    return (long double)(Square(p2.x) + Square(p2.y) - Square(p1.x) - Square(p1.y)) / (long double)(2 * (p2.x - p1.x));
}

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

    cin >> n >> l;
    for (int i = 1; i <= n; i++) {
        points[i].read();
    }

    i = 1;
    while (i <= n) {
        Point best_point = points[i];
        int pos_best_point = i;
        i++;
        while (i <= n && points[i].x == points[i - 1].x) {
            if (abs(points[i].y) < abs(best_point.y)) {
                best_point = points[i];
                pos_best_point = i;
            }
            i++;
        }

        if (ind_st >= 1 && WhereBetter(best_point, points[st[ind_st].first]) > l) {
            continue;
        }

        while (ind_st >= 1 && WhereBetter(best_point, points[st[ind_st].first]) < st[ind_st].second) {
            ind_st--;
        }

        if (ind_st == 0) {
            st[++ind_st] = { pos_best_point, 0 };
        }
        else {
            long double x = WhereBetter(best_point, points[st[ind_st].first]);
            st[++ind_st] = { pos_best_point, x };
        }
    }

    for (int i = 1; i <= ind_st; i++) {
        answer = max(answer, max(Distance(points[st[i].first], { st[i].second, 0 }), Distance(points[st[i].first], { (i == ind_st ? l : st[i + 1].second - EPS), 0 })));
    }
    cout << fixed << setprecision(6) << answer << '\n';

    return 0;
}

Subtask #1
4.0 / 4.0

#	Verdict	Memory	Grader output
1	Correct	600 KB	Output is correct
2	Correct	344 KB	Output is correct
3	Correct	348 KB	Output is correct
4	Correct	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	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	604 KB	Output is correct
3	Correct	1 ms	344 KB	Output is correct
4	Correct	1 ms	344 KB	Output is correct

Subtask #4
4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	604 KB	Output is correct
2	Correct	2 ms	604 KB	Output is correct
3	Correct	1 ms	604 KB	Output is correct
4	Correct	3 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	604 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	604 KB	Output is correct
2	Correct	2 ms	604 KB	Output is correct
3	Correct	1 ms	604 KB	Output is correct
4	Correct	2 ms	604 KB	Output is correct
5	Correct	1 ms	604 KB	Output is correct

Subtask #7
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	20 ms	2904 KB	Output is correct
2	Correct	21 ms	2804 KB	Output is correct
3	Correct	14 ms	2140 KB	Output is correct
4	Correct	23 ms	2736 KB	Output is correct
5	Correct	14 ms	1856 KB	Output is correct

Subtask #8
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	20 ms	2908 KB	Output is correct
2	Correct	20 ms	2472 KB	Output is correct
3	Correct	22 ms	2908 KB	Output is correct
4	Correct	27 ms	2768 KB	Output is correct
5	Correct	29 ms	3164 KB	Output is correct

Subtask #9
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	22 ms	5980 KB	Output is correct
2	Correct	22 ms	2896 KB	Output is correct
3	Correct	22 ms	4188 KB	Output is correct
4	Correct	38 ms	3408 KB	Output is correct
5	Correct	23 ms	3164 KB	Output is correct

Subtask #10
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	35 ms	3568 KB	Output is correct
2	Correct	27 ms	3416 KB	Output is correct
3	Correct	25 ms	3676 KB	Output is correct
4	Correct	33 ms	3412 KB	Output is correct
5	Correct	27 ms	3420 KB	Output is correct

Subtask #11
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	29 ms	4176 KB	Output is correct
2	Correct	27 ms	3416 KB	Output is correct
3	Correct	24 ms	3672 KB	Output is correct
4	Correct	32 ms	3408 KB	Output is correct
5	Correct	27 ms	3612 KB	Output is correct

Subtask #12
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	133 ms	31572 KB	Output is correct
2	Correct	133 ms	16056 KB	Output is correct
3	Correct	132 ms	16132 KB	Output is correct
4	Correct	168 ms	15960 KB	Output is correct
5	Correct	142 ms	15952 KB	Output is correct

Subtask #13
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	136 ms	15980 KB	Output is correct
2	Correct	138 ms	16732 KB	Output is correct
3	Correct	122 ms	17488 KB	Output is correct
4	Correct	153 ms	15900 KB	Output is correct
5	Correct	141 ms	15952 KB	Output is correct

Subtask #14
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	156 ms	37972 KB	Output is correct
2	Correct	171 ms	19024 KB	Output is correct
3	Correct	159 ms	19024 KB	Output is correct
4	Correct	191 ms	19024 KB	Output is correct
5	Correct	176 ms	19024 KB	Output is correct

Subtask #15
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	166 ms	19028 KB	Output is correct
2	Correct	176 ms	19900 KB	Output is correct
3	Correct	157 ms	20048 KB	Output is correct
4	Correct	190 ms	19048 KB	Output is correct
5	Correct	169 ms	19224 KB	Output is correct

Subtask #16
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	184 ms	44116 KB	Output is correct
2	Correct	186 ms	22144 KB	Output is correct
3	Correct	181 ms	22352 KB	Output is correct
4	Correct	225 ms	22356 KB	Output is correct
5	Correct	196 ms	22148 KB	Output is correct

Subtask #17
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	207 ms	22320 KB	Output is correct
2	Correct	202 ms	22984 KB	Output is correct
3	Correct	178 ms	24144 KB	Output is correct
4	Correct	224 ms	22352 KB	Output is correct
5	Correct	195 ms	22352 KB	Output is correct

Subtask #18
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	207 ms	50512 KB	Output is correct
2	Correct	214 ms	25276 KB	Output is correct
3	Correct	223 ms	25716 KB	Output is correct
4	Correct	268 ms	25620 KB	Output is correct
5	Correct	233 ms	25428 KB	Output is correct

Subtask #19
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	226 ms	25428 KB	Output is correct
2	Correct	249 ms	26148 KB	Output is correct
3	Correct	208 ms	27276 KB	Output is correct
4	Correct	265 ms	25292 KB	Output is correct
5	Correct	231 ms	25340 KB	Output is correct

Subtask #20
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	263 ms	63060 KB	Output is correct
2	Correct	269 ms	31748 KB	Output is correct
3	Correct	268 ms	31572 KB	Output is correct
4	Correct	325 ms	31560 KB	Output is correct
5	Correct	290 ms	31664 KB	Output is correct

Subtask #21
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	296 ms	31568 KB	Output is correct
2	Correct	275 ms	32364 KB	Output is correct
3	Correct	250 ms	34132 KB	Output is correct
4	Correct	339 ms	31636 KB	Output is correct
5	Correct	306 ms	31572 KB	Output is correct

Submission #1095261

Compilation message