Submission #853239

#TimeUsernameProblemLanguageResultExecution timeMemory
853239Youssif_ElkadiBalloons (CEOI11_bal)C++17
100 / 100
408 ms5592 KiB
#include <bits/stdc++.h> using namespace std; const int N = 5e5 + 3, mod = 1e9 + 7, inf = 1e9 + 5; double dist(double x1, double y1, double x2, double y2) { return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)); } double gimr(double x1, double y1, double x2, double y2) { double l = 0, r = y2, mid, ans = 0; for (int i=0;i<100;i++) { mid = (l + r) / 2; if (dist(x1, y1, x2, mid) >= y1 + mid) ans = max(ans, mid), l = mid; else r = mid; } return ans; } int main() { ios_base::sync_with_stdio(0), cin.tie(NULL), cout.tie(NULL); int n; cin >> n; stack<pair<double, double>> st; for (int i = 0; i < n; i++) { double x, r; cin >> x >> r; while (true) { if (st.size()) r = min(r, gimr(st.top().first, st.top().second, x, r)); else break; if (r > st.top().second) st.pop(); else break; } cout << fixed << setprecision(3) << r << "\n"; st.push({x, r}); } }
#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...