# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1221362 | juaquin_remon | Balloons (CEOI11_bal) | C++20 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
#include <iomanip>
#ifndef ONLINE_JUDGE
#include "debug.h"
#else
#define debug(...)
#define debugArr(...)
#endif
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef pair<ll,ll> pl;
#define forr(i,a,b) for(int i=int(a);i<int(b);++i)
#define forn(i,n) forr(i,0,n)
#define dforr(i,a,b) for(int i=int(b)-1;i>=int(a);--i)
#define dforn(i,n) dforr(i,0,n)
#define fore(e,c) for(const auto &e : (c))
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define fi first
#define se second
const ll MAXN = -1;
const ll mod = 1e9+7;
const ll inf = 1e18+10;
typedef long double ld;
struct Line {
mutable ld k, m, p;
bool operator<(const Line& o) const { return k < o.k; }
bool operator<(ll x) const { return p < x; }
};
struct LineContainer : multiset<Line, less<>> {
// (for doubles, use inf = 1/.0, div(a,b) = a/b)
ld inf = 1/.0;
ld div(ld a, ld b) { // floored division
return a / b; }
bool isect(iterator x, iterator y) {
if (y == end()) return x->p = inf, 0;
if (x->k == y->k) x->p = x->m > y->m ? inf : -inf;
else x->p = div(y->m - x->m, x->k - y->k);
return x->p >= y->p;
}
void add(ld k, ld m) {
auto z = insert({k, m, 0}), y = z++, x = y;
while (isect(y, z)) z = erase(z);
if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
while ((y = x) != begin() && (--x)->p >= y->p)
isect(x, erase(y));
}
ld query(ld x) {
assert(!empty());
auto l = *lower_bound(x);
return l.k * x + l.m;
}
};
void solve(){
ll n; cin >> n;
LineContainer lc;
forn(i, n) {
ll x, maxr;
cin >> x >> maxr;
cout << fixed << setprecision(3);
ld r;
if (i == 0) {
cout << maxr << "\n";
r = maxr;
} else {
ld sqrt_r_opt = -lc.query(x);
ld r_opt = sqrt_r_opt*sqrt_r_opt;
r = min((ld)maxr, r_opt);
cout << r << "\n";
}
ld sqrt_r = sqrtl(r);
lc.add(-1./(2*sqrt_r), x/(2*sqrt_r));
}
}
int main(){
ios::sync_with_stdio(0); cin.tie(0);
int tt = 1;
while(tt--) solve();
return 0;
}