Submission #659939

#	Time	Username	Problem	Language	Result	Execution time	Memory
659939		brobat	Balloons (CEOI11_bal)	C++17	100 / 100	160 ms	11700 KiB

bal

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define double long double

/*
Circle touches $(x, 0)$ and has radius $r$. Centre of circle would be $(x, r)$.
We have a previous circle with centre $(x0, r0)$ and radius $r0$. These two circles touch if distance between centres = sum of radii.
$ \sqrt{(x - x0)^2 + (r - r0)^2} = r + r0$.
or equivalently, 
$ (x - x0)^2 + (r - r0)^2 = (r + r0)^2$, or
$ (x - x0)^2 = 4*r*r0 $

Hence 

$$r = \frac{(x - x_{0})^2}{4*r_0}$$

r = (x - x0)^2 / 4*r0

At any given point, we need the minimum value of $r$ considering all circles $(x0, r0)$ that came before this circle.

One thing is for sure, we need to keep a monotonic stack which stores elements in increasing order of R from the end. (Top-most element should have minimum (r, x), then next element will have greater r but lower x, and so on).

Now, check if we can make R equal to the current top element of the stack. While we can, pop the top element of the stack! Then we get the final R, and push current circle into the stack, ez.
*/

double max_radius(pair<double, int>& c, int x) {
    return (c.second - x)*(c.second - x)*1.0/(4*c.first);
}

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);
    
    int n;
    cin >> n;
    vector<pair<int, double>> v(n);
    for(int i = 0; i < n; i++) {
        cin >> v[i].first >> v[i].second;
    }
    stack<pair<double, int>> s;
    for(int i = 0; i < n; i++) {
        double ans = v[i].second;
        while(!s.empty()) {
            if(s.top().first > ans) break;
            double mx = max_radius(s.top(), v[i].first);
            // cout << i << ' ' << s.top().first << ' ' << s.top().second << ' ' << mx << '\n';
            if(mx >= s.top().first) {
                s.pop();
                ans = min(ans, mx);
            }
            else break;
        }
        if(!s.empty()) ans = min(ans, max_radius(s.top(), v[i].first));
        cout << fixed << setprecision(3) << ans << '\n';
        s.push({ans, v[i].first});
    }
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10