Submission #1113949

#	Time	Username	Problem	Language	Result	Execution time	Memory
1113949		slycelote	Mobile (BOI12_mobile)	C++17	0 / 100	558 ms	24796 KiB

mobile

#include <cmath>
#include <iostream>
#include <vector>

using namespace std;

int main() {
    cin.tie(0); iostream::sync_with_stdio(false);

    int n, d; cin >> n >> d;
    vector<double> x, y;
    x.reserve(n); y.reserve(n);
    double R = 2e9, L1 = R, L2 = R;
    while (n--) {
        int xx, yy; cin >> xx >> yy;
        yy = abs(yy);
        if (!x.empty() && x.back() == xx) {
            y.back() = min(y.back(), (double)yy);
        } else {
            x.push_back(xx);
            y.push_back(yy);
        }
        auto d1 = hypot(xx, (double)yy);
        auto d2 = hypot(d-xx, (double)yy);
        R = min(R, max(d1, d2));
        L1 = min(L1, d1);
        L2 = min(L1, d2);
    }
    double L = max(L1, L2);
    n = x.size();
    while (R > L + 1e-3) {
        double M = L + (R-L)/2;
        vector<pair<double, double>> segs;
        for (int i = 0; i < n; ++i) if (M > y[i]) {
            double len = sqrt(M*M - y[i]*y[i]);
            double start = max(0.0, x[i] - len), end = min((double)d, x[i] + len);
            while (!segs.empty() && start <= segs.back().second) {
                start = min(start, segs.back().first);
                end = max(end, segs.back().second);
                segs.pop_back();
            }
            segs.push_back({start, end});
        }
        if (segs.empty() || segs.size() > 1 || segs.back().first > 0 || segs.back().second < d) {
            L = M;
        } else {
            R = M;
        }
    }

    cout << (L+R)/2 << endl;
}

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