Just OI-ACM

Balloons (Special Judge)

 
  • Apr 13, 2019

Problem

Source: 洛谷 P4697, CEOI 2011

Description

The organizers of CEOI 2011 are planning to hold a party with lots of balloons. There will be $n$ balloons, all sphere-shaped and lying in a line on the floor.

The balloons are yet to be inflated, and each of them initially has zero radius. Additionally, the $i$-th balloon is permanently attached to the floor at coordinate $x_i$. They are going to be inflated sequentially, from left to right. When a balloon is inflated, its radius is increased continuously until it reaches the upper bound for the balloon, $r_i$, or the balloon touches one of the previously inflated balloons.

The organizers would like to estimate how much air will be needed to inflate all the balloons. You are to find the final radius for each balloon.

img

Input

The first line of the standard input contains one integer $n (1 \leq n \leq 200 000)$ — the number of balloons.

The next n lines describe the balloons. The $i$-th of these lines contains two integers $x_i$ and $r_i$ $(0 \leq x_i \leq 10^9,1 \leq r_i \leq 10^9)$. You may assume that the balloons are given in a strictly increasing order of the $x$ coordinate.

In test data worth 40 points an additional inequality $n \leq 2000$ holds.

Output

Your program should output exactly $n$ lines, with the $i$-th line containing exactly one number — the radius of the $i$-th balloon after inflating. Your answer will be accepted if it differs from the correct one by no more than 0.001 for each number in the output.

Sample Input

3
0 9
8 1
13 7

Sample Output

9.000
1.000
4.694

 

Translation

Description

有 $n$ 个气球，他们一开始都是空的。

接下来，它们会按照从 1 到 $n$ 的顺序依次充气，其中第 $i$ 个气球与地面在 $x_i$ 位置接触。

当气球碰到碰到前面的某个气球，或者达到半径最大限制时，就会停止充气。其中第 $i$ 个气球的半径最大限制为 $r_i$。

现在请你求出，每个气球最终半径是多少。

数据规模：对于 $100 \%$ 的数据，保证 $1 \leq n \leq 200000$；$0 \leq x_i \leq 10^9$；$1 \leq r_i \leq 10^9$；$x_1 < x_2 < \dots < x_n$。

Input

第一行一个正整数 $n$，表示气球个数。

接下来 $n$ 行，每行两个空格隔开的整数 $x_i, r_i$。

Output

输出 $n$ 行，每行一个浮点数，第 $i$ 行的浮点数表示最终第 $i$ 个气球的半径。

你的答案会被判为正确，当且仅当与答案的绝对误差不超过 $10^{-3}$。

 

Solution

气球的横坐标是固定的，因此对于第 $i$ 个气球，当它与前 $i-1$ 个气球不相交时，可以推出其最大半径的公式（$j$ 为与 $i$ 相切的那个气球）：

\[\text{dist}(i,j) = \sqrt{(x(i) – x(j))^2 + (r(i) – r(j))^2} = r(i) + r(j)\] \[\Rightarrow r(i) = \frac{(x(i)–x(j))^2}{4 \times r(j)}\]

因此 $r[i] = \min \frac{(x(i)–x(j))^2}{4 \times r(j)} \quad (j < i)$

这样的做法时间复杂度为 $O(n^2)$。

然而，如果气球 $A$ 比气球 $B$ 更靠右 $(x(A)>x(B))$ 而且更大 $(r(A) \geq r(B))$，那么气球 $A$ 一定比气球 $B$ 优秀。所以我们可以忽略 $B$，只维护一个 $R$ 值严格单调递减的栈即可。

Code

Github (C++)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iomanip>
#include <cmath>
using namespace std;

const int M = 200005;
int n, top;
double x[M], r[M], q[M];

double Cal(int i, int j) {
  return (x[i] - x[j]) * (x[i] - x[j]) / (4 * r[j]);
}

int main() {
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> x[i] >> r[i];

    for(int i = 1; i <= n; i++) {
        while(top) {
            int j = q[top];
            r[i] = min(r[i], Cal(i,j));
            if(r[i] >= r[j]) top--;
            else break;
        }
        q[++top] = i;
    }
    for(int i = 1; i <= n; i++) cout << fixed << setprecision(5) << r[i] << endl;
    return 0;
}
Search