题解 P4697 【[CEOI2011]Balloons】

2019-05-23 09:27:58


$\large \color{#ff7daf}\texttt{CEOI2011 Balloons}$

先膜拜随机过题的大佬 $\texttt{Alpha}$

若圆 $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)$ ,证明略(其实挺显然的????)


#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;
}