题解 P4697 【[CEOI2011]Balloons】

#### [$\large \color{#ff7daf}\texttt{CEOI2011 Balloons}$](https://xc.fubuki.cn/2019/CEOI2011Balloons) 先膜拜随机过题的大佬 [$\texttt{Alpha}$](https://www.luogu.org/space/show?uid=87058) 。 若圆 $i$ 与圆 $j$ 相切，则 $r_i=\frac{(x_i-x_j)^2}{4r_j}$ ；若存在 $i,j$ 满足 $x_i>x_j,r_i>r_j$ ，则圆 $j$ 一定不会对后加入的点产生有效限制。因为题目保证 $x$ 递增，所以这里能用一个单调栈轻松维护。 接下来考虑决策。不难发现，若存在 $j$ 满足 $R(i, j)\leq r_j$ （其中 $R(i, j)$ 表示圆 $i$ 与圆 $j$ 相切时的 $r_i$ ），则所有 $j$ 之前的圆不会对 $i$ 产生有效限制；若 $R(i, j)>r_j$ ，则该限制可能是一个有效限制，并且一定有 $r_i > r_j$ ，可以直接从栈中删去 $j$ 。 时间复杂度 $O(n)$ ，证明略（其实挺显然的????） ```cpp #include <cstdio> #define maxn 200005 int n, stk[maxn], top; double r[maxn], x[maxn]; int main() { freopen("test.in", "r", stdin); freopen("test.out", "w", stdout); scanf("%d", &n); for (int i = 1; i <= n; ++i) { scanf("%lf%lf", &x[i], &r[i]); while (top > 0) { int j = stk[top]; double now = (x[i] - x[j]) / 4.0 / r[j] * (x[i] - x[j]); r[i] = now < r[i] ? now : r[i]; if (r[i] <= r[j]) break; else --top; } stk[++top] = i; printf("%.6lf\n", r[i]); } return 0; } ```