제출 #1261301

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1261301		MisterReaper	Mobile (BOI12_mobile)	C++17	100 / 100	153 ms	20208 KiB

mobile

// File A.cpp created on 20.08.2025 at 00:54:27
#include <bits/stdc++.h>

using i64 = long long;
using ld = long double;

#ifdef DEBUG 
    #include "/home/ahmetalp/Desktop/Workplace/debug.h"
#else
    #define debug(...) void(23)
#endif

ld sq(ld x) {
    return x * x;
}

i64 sq(i64 x) {
    return x * x;
}

ld inter_2d(i64 x1, i64 y1, i64 x2, i64 y2) {
    return ld(sq(x1) + sq(y1) - sq(x2) - sq(y2)) / (2 * (x1 - x2));
}

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

    std::cout << std::fixed << std::setprecision(9);

    int N, M;
    std::cin >> N >> M;

    std::vector<std::array<i64, 2>> A(N);
    for (int i = 0; i < N; ++i) {
        std::cin >> A[i][0] >> A[i][1];
        A[i][1] = std::abs(A[i][1]);
    }

    auto inter = [&](auto lhs, auto rhs) -> ld {
        return inter_2d(A[lhs][0], A[lhs][1], A[rhs][0], A[rhs][1]);
    };

    std::deque<int> stk;

    for (int i = 0; i < N; ++i) {
        if (!stk.empty() && A[stk.back()][0] == A[i][0]) {
            if (A[stk.back()][1] >= A[i][1]) {
                stk.pop_back();
            } else {
                continue;
            }
        }
        while (stk.size() > 1 && inter(stk.end()[-2], stk.back()) > inter(stk.back(), i)) {
            stk.pop_back();
        }
        stk.emplace_back(i);
    }

    while (stk.size() > 1 && inter(stk[0], stk[1]) < 0) {
        stk.pop_front();
    }
    while (stk.size() > 1 && inter(stk.end()[-2], stk.back()) > M) {
        stk.pop_back();
    }

    ld res = 0;

    for (int i = 0; i < stk.size(); ++i) {
        ld l = (i == 0 ? 0 : inter(stk[i - 1], stk[i]));
        ld r = (i + 1 == stk.size() ? M : inter(stk[i], stk[i + 1]));
        res = std::max(res, std::sqrt(sq(A[stk[i]][1]) + sq(A[stk[i]][0] - l)));
        res = std::max(res, std::sqrt(sq(A[stk[i]][1]) + sq(A[stk[i]][0] - r)));
    }

    std::cout << res << '\n';

    return 0;
}

• Subtask 1: 4 / 4
• Subtask 2: 4 / 4
• Subtask 3: 4 / 4
• Subtask 4: 4 / 4
• Subtask 5: 4 / 4
• Subtask 6: 5 / 5
• Subtask 7: 5 / 5
• Subtask 8: 5 / 5
• Subtask 9: 5 / 5
• Subtask 10: 5 / 5
• Subtask 11: 5 / 5
• Subtask 12: 5 / 5
• Subtask 13: 5 / 5
• Subtask 14: 5 / 5
• Subtask 15: 5 / 5
• Subtask 16: 5 / 5
• Subtask 17: 5 / 5
• Subtask 18: 5 / 5
• Subtask 19: 5 / 5
• Subtask 20: 5 / 5
• Subtask 21: 5 / 5