Submission #1011174

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1011174	2024-06-30T03:44:26 Z	vjudge1	Mobile (BOI12_mobile)	C++17	66 / 100	314 ms	19620 KB

mobile

#include <bits/stdc++.h>
using i64 = long long;

struct Point {
    double x, y;
};

double dist(const Point &a, const Point &b) {
    double dx = a.x - b.x;
    double dy = a.y - b.y;
    return std::sqrt(dx * dx + dy * dy);
}

double insec(const Point &a, const Point &b) {
    double t1 = b.x * b.x + b.y * b.y - a.x * a.x - a.y * a.y;
    double t2 = b.x - a.x;
    return t1 / t2 / 2;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    double l;
    std::cin >> n >> l;

    std::deque<Point> pt;
    for (int i = 0; i < n; i++) {
        double x, y;
        std::cin >> x >> y;
        y = std::abs(y);

        if (pt.size() && pt.back().x == x) {
            if (pt.back().y <= y) {
                continue;
            } else {
                pt.pop_back();
            }
        }

        Point cur{x, y};
        while ((int)pt.size() > 1 && insec(pt[pt.size() - 1], pt[pt.size() - 2]) > insec(pt[pt.size() - 1], cur)) {
            pt.pop_back();
        }

        pt.emplace_back(cur);
    }

    while ((int)pt.size() > 1 && insec(pt[0], pt[1]) < 0) {
        pt.pop_front();
    }
    while ((int)pt.size() > 1 && insec(pt[pt.size() - 1], pt[pt.size() - 2]) > l) {
        pt.pop_back();
    }

    double ans = 0;
    Point lt{0, 0}, rt{l, 0};
    for (int i = 0; i < (int)pt.size(); i++) {
        if (i > 0) {
            lt.x = insec(pt[i], pt[i - 1]);
        }
        if (i + 1 < (int)pt.size()) {
            rt.x = insec(pt[i], pt[i + 1]);
        }
        if (lt.x < 0 || lt.x > l || rt.x < 0 || rt.x > l) {
            continue;
        }
        ans = std::max({ans, dist(lt, pt[i]), dist(pt[i], rt)});
    }
    std::cout << std::fixed << std::setprecision(6) << ans << "\n";

    return 0;
}

Subtask #1
4.0 / 4.0

#	Verdict	Memory	Grader output
1	Correct	348 KB	Output is correct
2	Correct	408 KB	Output is correct
3	Correct	348 KB	Output is correct
4	Correct	344 KB	Output is correct

Subtask #2
4.0 / 4.0

#	Verdict	Memory	Grader output
1	Correct	348 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Correct	348 KB	Output is correct
4	Correct	348 KB	Output is correct

Subtask #3
0 / 4.0

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

Subtask #4
4.0 / 4.0

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

Subtask #5
4.0 / 4.0

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

Subtask #6
5.0 / 5.0

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

Subtask #7
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	20 ms	348 KB	Output is correct
2	Correct	23 ms	1332 KB	Output is correct
3	Correct	19 ms	860 KB	Output is correct
4	Correct	23 ms	1584 KB	Output is correct
5	Correct	12 ms	600 KB	Output is correct

Subtask #8
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	19 ms	348 KB	Output is correct
2	Correct	20 ms	1116 KB	Output is correct
3	Correct	23 ms	1456 KB	Output is correct
4	Correct	29 ms	1628 KB	Output is correct
5	Correct	28 ms	1880 KB	Output is correct

Subtask #9
0 / 5.0

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

Subtask #10
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	28 ms	348 KB	Output is correct
2	Correct	26 ms	460 KB	Output is correct
3	Correct	24 ms	1624 KB	Output is correct
4	Correct	35 ms	2396 KB	Output is correct
5	Correct	28 ms	1724 KB	Output is correct

Subtask #11
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	29 ms	1372 KB	Output is correct
2	Correct	27 ms	1628 KB	Output is correct
3	Correct	23 ms	1628 KB	Output is correct
4	Correct	33 ms	2348 KB	Output is correct
5	Correct	28 ms	1628 KB	Output is correct

Subtask #12
0 / 5.0

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

Subtask #13
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	119 ms	348 KB	Output is correct
2	Correct	134 ms	7684 KB	Output is correct
3	Correct	119 ms	7684 KB	Output is correct
4	Correct	167 ms	9556 KB	Output is correct
5	Correct	146 ms	7504 KB	Output is correct

Subtask #14
0 / 5.0

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

Subtask #15
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	138 ms	348 KB	Output is correct
2	Correct	155 ms	1220 KB	Output is correct
3	Correct	148 ms	8276 KB	Output is correct
4	Correct	183 ms	12112 KB	Output is correct
5	Correct	159 ms	9132 KB	Output is correct

Subtask #16
0 / 5.0

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

Subtask #17
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	181 ms	348 KB	Output is correct
2	Correct	188 ms	10576 KB	Output is correct
3	Correct	203 ms	10836 KB	Output is correct
4	Correct	210 ms	13652 KB	Output is correct
5	Correct	209 ms	10324 KB	Output is correct

Subtask #18
0 / 5.0

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

Subtask #19
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	243 ms	344 KB	Output is correct
2	Correct	216 ms	11972 KB	Output is correct
3	Correct	185 ms	11860 KB	Output is correct
4	Correct	259 ms	15696 KB	Output is correct
5	Correct	221 ms	11860 KB	Output is correct

Subtask #20
0 / 5.0

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

Subtask #21
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	242 ms	348 KB	Output is correct
2	Correct	294 ms	14684 KB	Output is correct
3	Correct	247 ms	15236 KB	Output is correct
4	Correct	314 ms	19620 KB	Output is correct
5	Correct	262 ms	15188 KB	Output is correct

Submission #1011174

Compilation message