Submission #973324

#TimeUsernameProblemLanguageResultExecution timeMemory
973324IdanRosenMobile (BOI12_mobile)C++98
0 / 100
1078 ms47336 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll, ll> pll; typedef long double ld; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); ll n, l; cin >> n >> l; vector<pll> arr(n); for (auto &ref: arr) cin >> ref.first >> ref.second; ld start = 0; ld end = 1.42e9; while (end - start > 1e-4) { ld mid = start + (end - start) / 2; bool check = false; { vector<pair<ld, ld>> ranges(n); 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[i] = {center - delta, center + delta}; } if (ranges.empty()) { check = false; } else { std::sort(ranges.begin(), ranges.end()); vector<pair<ld, ld>> 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 <= 0 && 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...