Submission #1258983

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258983		aditya_k47	Mobile (BOI12_mobile)	C++20	15 / 100	282 ms	99544 KiB

mobile

#include <bits/stdc++.h>
using namespace std;

struct Line {
    long double a, b;     // y = a*x + b
    long double start;    // from which x this line becomes the minimum on the envelope
    Line(long double a_=0, long double b_=0, long double s_=-INFINITY) : a(a_), b(b_), start(s_) {}
    inline long double value(long double x) const { return a*x + b; }
};

// intersection x-coordinate where l2 becomes better than l1
static inline long double intersectX(const Line& l1, const Line& l2) {
    // assume l1.a != l2.a
    return (l2.b - l1.b) / (l1.a - l2.a);
}

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

    int N;
    long long L_in;
    if (!(cin >> N >> L_in)) return 0;
    long double L = (long double)L_in;

    vector<pair<long long,long long>> pts;
    pts.reserve(N);
    for (int i = 0; i < N; ++i) {
        long long xi, yi;
        cin >> xi >> yi;
        pts.emplace_back(xi, yi);
    }

    // Build lines with slopes a = -2*xi (nonincreasing since xi nondecreasing),
    // intercept b = xi^2 + yi^2 (use long double to avoid overflow).
    vector<Line> hull; hull.reserve(N);
    auto addLine = [&](long double a, long double b) {
        // If slope equals last slope, keep only the one with smaller intercept (better for min)
        if (!hull.empty() && fabsl(hull.back().a - a) < 1e-18L) {
            if (b >= hull.back().b) return; // worse or equal: discard
            // better: replace last
            hull.back() = Line(a, b, hull.back().start);
            return;
        }
        Line cur(a, b, -INFINITY);
        while (!hull.empty()) {
            long double x = intersectX(hull.back(), cur);
            if (x <= hull.back().start) {
                hull.pop_back();
            } else {
                cur.start = x;
                break;
            }
        }
        if (hull.empty()) cur.start = -INFINITY;
        hull.push_back(cur);
    };

    for (int i = 0; i < N; ++i) {
        long double xi = (long double)pts[i].first;
        long double yi = (long double)pts[i].second;
        long double a = -2.0L * xi;
        long double b = xi*xi + yi*yi;
        addLine(a, b);
    }

    // Gather candidate x's: 0, L, and the starts of hull lines clipped into [0, L],
    // plus also the next starts (segment ends) when they lie in [0, L].
    vector<long double> cand;
    cand.push_back(0.0L);
    cand.push_back(L);

    for (size_t i = 0; i < hull.size(); ++i) {
        long double left = hull[i].start;
        long double right = (i + 1 < hull.size()) ? hull[i+1].start : INFINITY;

        // clip segment [left, right) to [0, L]
        long double a = max(left, (long double)0.0L);
        long double b = min(right, L);
        if (a <= L && b >= 0.0L && a <= b) {
            // check endpoints a and b
            cand.push_back(a);
            cand.push_back(b);
        }
    }

    // Deduplicate candidates (optional)
    sort(cand.begin(), cand.end());
    cand.erase(unique(cand.begin(), cand.end(), [](long double x, long double y){
        return fabsl(x - y) < 1e-12L;
    }), cand.end());

    // For querying m(x) = min_i (a_i x + b_i), we can binary search which line is active
    // because hull[i].start are increasing.
    auto m_of_x = [&](long double x) -> long double {
        size_t lo = 0, hi = hull.size();
        while (lo + 1 < hi) {
            size_t mid = (lo + hi) / 2;
            if (x >= hull[mid].start) lo = mid;
            else hi = mid;
        }
        return hull[lo].value(x);
    };

    long double best = 0.0L;
    for (long double x : cand) {
        long double val = x*x + m_of_x(x); // squared distance at worst-case nearest tower
        if (val > best) best = val;
    }

    cout.setf(std::ios::fixed); cout << setprecision(10) << sqrt((long double)best) << "\n";
    return 0;
}

• 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: 5 / 5
• Subtask 11: 5 / 5
• Subtask 12: 0 / 5
• Subtask 13: 0 / 5
• Subtask 14: 0 / 5
• Subtask 15: 5 / 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