Submission #1249014

#TimeUsernameProblemLanguageResultExecution timeMemory
1249014mirbek01Mobile (BOI12_mobile)C++20
15 / 100
649 ms20172 KiB
#include <bits/stdc++.h> using namespace std; 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]; } 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; } else { 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++) { double left = 0, right = L; if (i) { left = get_point(stk[i - 1], stk[i]); } if (i + 1 < stk.size()) { right = get_point(stk[i], stk[i + 1]); } if (left < 0 || right > L || left > L || right < 0) continue; ans = max(ans, dist(x[stk[i]], y[stk[i]], left, 0)); ans = max(ans, dist(x[stk[i]], y[stk[i]], right, 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...