Submission #941494

#TimeUsernameProblemLanguageResultExecution timeMemory
941494dwuyBalloons (CEOI11_bal)C++14
100 / 100
644 ms13652 KiB
#include <bits/stdc++.h> #define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL) #define file(a) freopen(a".inp","r",stdin); freopen(a".out", "w",stdout) #define fi first #define se second #define endl "\n" #define len(s) int32_t(s.length()) #define MASK(k)(1LL<<(k)) #define TASK "test" #define int long long #define double long double using namespace std; typedef tuple<int, int, int> tpiii; typedef pair<double, double> pdd; typedef pair<int, int> pii; typedef long long ll; const long long OO = 1e18; const int MOD = 1e9 + 7; const int INF = 1e9; const int MX = 200005; int n; pdd a[MX]; pdd v[MX]; void nhap(){ cin >> n; for(int i=1; i<=n; i++) cin >> a[i].fi >> a[i].se; } double sqr(double x){ return x*x; } double euler(pdd a, pdd b){ return sqrt(sqr(a.fi - b.fi) + sqr(a.se - b.se)); } double dis(pdd ball, double p){ double lo=0, hi=INF; for(int t=0; t<65; t++){ double mid = (lo+hi)/2; if(euler(ball, {p, mid}) >= mid + ball.se) lo = mid; else hi = mid; } return (lo + hi)/2; } void solve(){ stack<pdd> v; for(int i=1; i<=n; i++){ double val = a[i].se; while(v.size()){ val = min({val, dis(v.top(), a[i].fi)}); if(val >= v.top().se) v.pop(); else break; } v.push({a[i].fi, val}); cout << fixed << setprecision(3) << val << '\n'; } } int32_t main(){ fastIO; //file(TASK); nhap(); solve(); 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...