题解

思路概述

• 气球按横坐标递增依次充气。第 $i$ 个气球最终半径是它的上限 $r_i$ 和与前面某个气球相切时的半径两者取较小值。若它与编号 $j<i$ 的气球相切，则满足$$(y_i + y_j)^2 = (x_i - x_j)^2 \quad\Rightarrow\quad y_i = \frac{(x_i-x_j)^2}{4y_j}. $$因为只关心最终半径，我们可以在处理第 $i$ 个时，考虑所有可能限制它的前驱。
• 注意到若某个旧气球最终半径不小于当前求得的 y[i]，那么它永远不会限制后续气球（因为它更大且更靠左），可以直接从候选集合里移除。于是可以维护一个单调栈，栈内气球的最终半径严格递增，且只有它们可能限制后续的新气球。

实现细节

• 顺序读入气球，初始半径 y[i]=r[i]。不断和栈顶气球尝试“相切半径”，若更小则更新 y[i]；若栈顶气球最终半径不超过新的 y[i]，说明它已经不会比当前气球更“突出”，将其弹出后继续比较下一位。
• 循环结束后输出 y[i] 并把当前气球压入栈。由于每个气球最多进栈出栈一次，总体是线性的。
• 需要使用 long double 维护精度，题面要求误差在 $10^{-3}$ 以内，直接用常规浮点输出即可。

复杂度

排序已给定，线性扫描每个气球最多被压栈和弹栈各一次，时间复杂度 $O(n)$，空间复杂度 $O(n)$。

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
using f64 = long double;
i64 n,x[200009],r[200009];
long double y[200009];
vector<int> st;
f64 calc(int i,int j) {return (x[i]-x[j])*(x[i]-x[j])/4.0L/y[i];}
int main()
{
    if(fopen("D:/CPP/THEMIS/test.inp","r"))
    {
        freopen("D:/CPP/THEMIS/test.inp","r",stdin);
        freopen("D:/CPP/THEMIS/test.out","w",stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n; cout<<fixed<<setprecision(3);
    for(int i=1;i<=n;++i) cin>>x[i]>>r[i];
    for(int i=1;i<=n;++i)
    {
        y[i]=r[i];
        while(!st.empty())
        {
            y[i]=min(y[i],calc(st.back(),i));
            if(y[i]>=y[st.back()]) st.pop_back();
            else break;
        }
        cout<<y[i]<<"\n";
        st.push_back(i);
    }
    //for(int i=1;i<st.size();++i) assert(y[st[i-1]]>=y[st[i]]);
}