Submission #1236461

#TimeUsernameProblemLanguageResultExecution timeMemory
1236461MinhKienBalloons (CEOI11_bal)C++20
60 / 100
637 ms4928 KiB
#include <iostream> #include <math.h> #include <stack> using namespace std; struct bb { long double x, r; bb () {} bb (long double X, long double R) { x = X; r = R; } }; int n; bb k; stack <bb> st, tmp; long double dis(bb A, bb B) { return sqrt((A.x - B.x) * (A.x - B.x) + (A.r - B.r) * (A.r - B.r)); } long double Find(bb kt) { return (kt.x - k.x) * (kt.x - k.x) / (4.0 * kt.r); } int main() { cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false); cin >> n; for (int i = 1; i <= n; ++i) { cin >> k.x >> k.r; long double ans; if (st.empty()) { printf("%.3Lf\n", k.r); ans = k.r; } else { ans = k.r; int cnt = 0; while (!st.empty()) { ++cnt; if (cnt > 400) break; ans = min(ans, Find(st.top())); tmp.push(st.top()); st.pop(); } while (!tmp.empty()) { st.push(tmp.top()); tmp.pop(); } while (!st.empty() && st.top().r < ans) st.pop(); printf("%.3Lf\n", ans); } st.push(bb(k.x, ans)); } 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...