oj.uz

Submission #659939

# Submission time Handle Problem Language Result Execution time Memory
659939 2022-11-19T23:51:12 Z brobat Balloons (CEOI11_bal) C++17
100 / 100
 160 ms 11700 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB 10 numbers

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB 2 numbers

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB 505 numbers

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB 2000 numbers

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 1108 KB 20000 numbers

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 2644 KB 50000 numbers
2 Correct 39 ms 3156 KB 49912 numbers

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 4500 KB 100000 numbers

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 5260 KB 115362 numbers
2 Correct 97 ms 7148 KB 119971 numbers

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 6616 KB 154271 numbers
2 Correct 159 ms 11700 KB 200000 numbers

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 8140 KB 200000 numbers
2 Correct 156 ms 11696 KB 199945 numbers