Submission #973329

#TimeUsernameProblemLanguageResultExecution timeMemory
973329IdanRosenMobile (BOI12_mobile)C++98
0 / 100
1077 ms82204 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef pair<ld, ld> pld; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); ll n, l; cin >> n >> l; vector<pld> arr(n); for (auto &ref: arr) cin >> ref.first >> ref.second; ld start = 0; ld end = 1.42e9; while (end - start > 1e-6) { ld mid = start + (end - start) / 2; bool check = false; { vector<pld> ranges; for (int i = 0; i < n; i++) { if (mid < arr[i].second) continue; ld center = arr[i].first; ld delta = sqrt(mid * mid - (ld) (arr[i].second * arr[i].second)); ranges.push_back({center - delta, center + delta}); } if (ranges.empty()) { check = false; } else { std::sort(ranges.begin(), ranges.end()); vector<pld> intersects; for (int i = 0; i < n; i++) { if (intersects.empty()) intersects.push_back(ranges[i]); else { if (ranges[i].first <= intersects.back().second) { intersects.back().second = max(intersects.back().second, ranges[i].second); } else intersects.push_back(ranges[i]); } } for (auto& seg : intersects) { if ((seg.first <= (ld) 0) && ((ld) l <= seg.second)) { check = true; break; } } } } if (check) end = mid; else start = mid; } cout << fixed << setprecision(6) << start << endl; }
#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...