题目描述

:::align{right} :::

皮克斯（Pixar）正准备在 2023 年戛纳电影节上推出其下一部动画电影《疯狂元素城》（Elemental）。但其中一个场景需要重新渲染。在这个场景中，有 $n$ 张多米诺骨牌排成一条直线，其中一张骨牌应该倒下，并以多米诺骨牌的方式推倒后续的若干张骨牌。考虑到距离 2023 年戛纳电影节已不足 1 个月，皮克斯请你编写一个程序，计算为 $n$ 种不同的初始骨牌选择重新渲染场景的成本。

为了简化计算，我们假设多米诺骨牌从侧面看像是坐标轴上没有宽度的线段，并且它们向左倒下。骨牌从左到右编号，第 $i$ 张骨牌的高度为 $l_{i}$，位于 $x_{i}$。重新渲染此场景的成本等于场景中运动部分的面积，即被推倒骨牌的四分之一圆区域的并集面积。请注意，骨牌倒下的区域可能重叠，重叠的面积只应计算一次。图片说明了第一个样例测试中多米诺骨牌的倒下过程，此时选择的初始倒下骨牌是编号为 5 的骨牌。

输入格式

输入的第一行包含一个正整数 $n$，表示多米诺骨牌的数量。接下来的 $n$ 行，每行包含一对整数 $x_{i}$ 和 $l_{i}$，表示第 $i$ 张骨牌的位置和高度。保证 $n \leqslant 200,000$ 且 $1 \leqslant x_{i}, l_{i} \leqslant 10^{9}$。骨牌按从左到右的顺序给出；即 $x_{i} < x_{i+1}$。

输出格式

输出 $n$ 行，其中第 $i$ 行包含以第 $i$ 张骨牌作为初始倒下骨牌时重新渲染场景的成本。所有数字的绝对误差或相对误差必须不超过 $10^{-6}$。

7
2 2
5 3
9 5
12 1
13 5
14 2
16 3

3.141592654
7.068583471
24.659773696
0.785398163
42.250963921
44.164186876
49.714124052

提示

翻译由 DeepSeek V3.2 完成