Submission #1330385

#	Time	Username	Problem	Language	Result	Execution time	Memory
1330385		randi_pav	Mobile (BOI12_mobile)	C++20	100 / 100	349 ms	127156 KiB

mobile

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

typedef long double ld;

int main() {
    ios::sync_with_stdio(0); cin.tie(0); 
    int n; ld l;
    if (!(cin >> n >> l)) return 0;

    vector<pair<ld, ld>> all_towers(n);
    for (int i = 0; i < n; i++) cin >> all_towers[i].first >> all_towers[i].second;

    
    vector<pair<ld, ld>> towers;
    for (auto &t : all_towers) {
        if (!towers.empty() && towers.back().first == t.first) {
            if (abs(t.second) < abs(towers.back().second)) towers.back() = t;
        } else towers.push_back(t);
    }

  
    vector<pair<ld, ld>> hull;
    vector<ld> intersections;

    auto get_x = [](pair<ld, ld> a, pair<ld, ld> b) {
        return (b.first * b.first + b.second * b.second - a.first * a.first - a.second * a.second) / (2.0 * (b.first - a.first));
    };

    for (auto &t : towers) {
        while (hull.size() >= 2) {
            ld x_new = get_x(hull.back(), t);
            if (x_new <= intersections.back()) {
                hull.pop_back();
                intersections.pop_back();
            } else break;
        }
        if (!hull.empty()) intersections.push_back(get_x(hull.back(), t));
        hull.push_back(t);
    }

  
    ld max_ans = 0;
    auto get_dist = [](pair<ld, ld> t, ld x) {
        return sqrtl((t.first - x) * (t.first - x) + t.second * t.second);
    };

   
    int start_idx = 0;
    while(start_idx < intersections.size() && intersections[start_idx] < 0) start_idx++;
    max_ans = max(max_ans, get_dist(hull[start_idx], 0));

   
    int end_idx = hull.size() - 1;
    while(end_idx > 0 && intersections[end_idx - 1] > l) end_idx--;
    max_ans = max(max_ans, get_dist(hull[end_idx], l));


    for (int i = 0; i < (int)intersections.size(); i++) {
        if (intersections[i] > 0 && intersections[i] < l) {
            max_ans = max(max_ans, get_dist(hull[i], intersections[i]));
        }
    }

    cout << fixed << setprecision(6) << (double)max_ans << endl;
    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