Submission #1249013

#TimeUsernameProblemLanguageResultExecution timeMemory
1249013mirbek01Mobile (BOI12_mobile)C++20
0 / 100
590 ms28016 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, 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])); }; vector <double> start(n); deque <int> stk; for (int i = 0; i < n; i++) { while (stk.size() > 1 && get_point(stk.back(), i) <= get_point(stk.back(), stk[stk.size() - 2])) stk.pop_back(); if (!stk.empty() && x[stk.back()] == x[i]) { continue; } if (!stk.empty()) start[i] = get_point(stk.back(), i); 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(6) << 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...