Submission #927926

#TimeUsernameProblemLanguageResultExecution timeMemory
927926TAhmed33Mobile (BOI12_mobile)C++98
100 / 100
209 ms41656 KiB
#include <bits/stdc++.h> using namespace std; #define int long long typedef long double ld; int n, l; ld inter (pair <int, int> &a, pair <int, int> &b) { return 1.0 * (a.second - b.second) / (b.first - a.first); } const ld eps = 1e-9; ld get (pair <int, int> &a, ld b, ld c) { return max(b * b + a.first * b + a.second, c * c + a.first * c + a.second); } vector <pair <int, int>> dd; deque <pair <int, int>> hull; signed main () { ios::sync_with_stdio(0); cin.tie(0); cin >> n >> l; cout << fixed << setprecision(9); for (int i = 0; i < n; i++) { int a, b; cin >> a >> b; int m = -2 * a; int c = a * a + b * b; dd.push_back({m, c}); } sort(dd.begin(), dd.end()); int prev = -1e9 + 7; for (auto i : dd) { pair <int, int> x = i; if (x.first == prev) continue; prev = x.first; if (hull.size() < 2) { hull.push_front(x); continue; } while (hull.size() >= 2) { ld a = inter(hull[0], hull[1]), b = inter(x, hull[0]); if (a + eps < b) { hull.pop_front(); } else { break; } } hull.push_front(x); } while (hull.size() >= 2) { if (inter(hull[0], hull[1]) < eps) hull.pop_front(); else break; } while (hull.size() >= 2) { if (inter(hull.back(), hull[hull.size() - 2]) > l + eps) hull.pop_back(); else break; } ld ans = 0; if (hull.size() == 1) { ans = get(hull[0], 0, l); cout << sqrt(ans) << '\n'; return 0; } ans = max(get(hull[0], 0, inter(hull[0], hull[1])), get(hull.back(), inter(hull.back(), hull[hull.size() - 2]), l)); for (int i = 1; i < (int)hull.size() - 1; i++) { ans = max(ans, get(hull[i], inter(hull[i], hull[i - 1]), inter(hull[i], hull[i + 1]))); } cout << sqrt(ans) << '\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...