Submission #1249029

#TimeUsernameProblemLanguageResultExecution timeMemory
1249029mirbek01Mobile (BOI12_mobile)C++20
100 / 100
688 ms35832 KiB
#include <bits/stdc++.h> using namespace std; #define double long double double dist(double x, double y, double a, double b) { return sqrt((x - a) * (x - a) + (y - b) * (y - b)); } signed main() { int n; double L; cin >> n >> L; vector <double> x(n), y(n); for (int i = 0; i < n; i++) { cin >> x[i] >> y[i]; y[i] = abs(y[i]); } auto get_point = [&](int i, int j) { return ((x[i] * x[i] + y[i] * y[i]) - (x[j] * x[j] + y[j] * y[j])) / (2.0 * (x[i] - x[j])); }; deque <int> stk; for (int i = 0; i < n; i++) { if (!stk.empty() && x[stk.back()] == x[i]) { if (y[i] >= y[stk.back()]) { continue; } stk.pop_back(); } while (stk.size() > 1 && get_point(stk.back(), i) < get_point(stk[stk.size() - 2], stk.back())) stk.pop_back(); stk.push_back(i); } while (stk.size() > 1 && get_point(stk[0], stk[1]) < 0) { stk.pop_front(); } while (stk.size() > 1 && get_point(stk[stk.size() - 2], stk[stk.size() - 1]) > L) { stk.pop_back(); } double ans = 0; for (int i = 0; i < stk.size(); i++) { if (i) { if (get_point(stk[i - 1], stk[i]) < 0 || get_point(stk[i - 1], stk[i]) > L) continue; ans = max(ans, dist(x[stk[i]], y[stk[i]], get_point(stk[i - 1], stk[i]), 0)); } else { ans = max(ans, dist(x[stk[i]], y[stk[i]], 0, 0)); } if (i + 1 < stk.size()) { if (get_point(stk[i], stk[i + 1]) < 0 || get_point(stk[i], stk[i + 1]) > L) continue; ans = max(ans, dist(x[stk[i]], y[stk[i]], get_point(stk[i], stk[i + 1]), 0)); } else { ans = max(ans, dist(x[stk[i]], y[stk[i]], L, 0)); } } cout << fixed << setprecision(3) << ans << 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...