题解 P4697 【[CEOI2011]Balloons】
吹雪吹雪吹
2019-05-23 09:27:58
#### [$\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;
}
```