제출 #1324405

#제출 시각아이디문제언어결과실행 시간메모리
1324405jack205Mobile (BOI12_mobile)C++20
50 / 100
1097 ms48336 KiB
#include <bits/stdc++.h>
using namespace std;

// -------- Fast Scanner (fread) --------
struct FastScanner {
    static const int BUFSIZE = 1 << 20;
    int idx, size;
    char buf[BUFSIZE];
    FastScanner() : idx(0), size(0) {}
    inline char read() {
        if (idx >= size) {
            size = (int)fread(buf, 1, BUFSIZE, stdin);
            idx = 0;
            if (size == 0) return 0;
        }
        return buf[idx++];
    }
    template <class T>
    bool readInt(T &out) {
        char c;
        do {
            c = read();
            if (!c) return false;
        } while (c <= ' ');

        bool neg = false;
        if (c == '-') { neg = true; c = read(); }

        T val = 0;
        while (c > ' ') {
            val = val * 10 + (c - '0');
            c = read();
        }
        out = neg ? -val : val;
        return true;
    }
};

static const long double EPS = 1e-12L;

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

    FastScanner fs;

    int N;
    long long L;
    if (!fs.readInt(N)) return 0;
    fs.readInt(L);

    vector<long long> X(N), Y(N);
    for (int i = 0; i < N; i++) {
        fs.readInt(X[i]);
        fs.readInt(Y[i]);
    }

    // intervals buffer reused each check to avoid realloc cost
    vector<pair<long double, long double>> segs;
    segs.reserve(N);

    auto check = [&](long double R) -> bool {
        segs.clear();
        long double R2 = R * R;

        for (int i = 0; i < N; i++) {
            long double yi = (long double)Y[i];
            long double ay = fabsl(yi);
            if (ay > R + EPS) continue;

            long double inside = R2 - yi * yi;
            if (inside < 0) inside = 0; // guard for precision
            long double dx = sqrtl(inside);

            long double li = (long double)X[i] - dx;
            long double ri = (long double)X[i] + dx;

            if (ri <= 0.0L + EPS || li >= (long double)L - EPS) continue;
            if (li < 0.0L) li = 0.0L;
            if (ri > (long double)L) ri = (long double)L;

            segs.emplace_back(li, ri);
        }

        if (segs.empty()) return false;

        sort(segs.begin(), segs.end(),
             [](const auto &a, const auto &b) {
                 if (a.first != b.first) return a.first < b.first;
                 return a.second > b.second;
             });

        long double cur = 0.0L;
        for (auto &pr : segs) {
            long double l = pr.first, r = pr.second;
            if (l > cur + 1e-11L) return false; // gap
            if (r > cur) cur = r;
            if (cur >= (long double)L - 1e-11L) return true;
        }
        return cur >= (long double)L - 1e-11L;
    };

    // Binary search on R (real)
    long double lo = 0.0L;
    // Safe upper bound (coords up to ~1e9 usually; this is intentionally generous)
    long double hi = 2.5e9L;

    // Fixed iterations (avoid while(hi-lo) because of long double and speed)
    for (int it = 0; it < 60; it++) {
        long double mid = (lo + hi) / 2.0L;
        if (check(mid)) hi = mid;
        else lo = mid;
    }

    cout.setf(std::ios::fixed); 
    cout << setprecision(10) << (double)hi << "\n";
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...