← 返回题目列表

Codeforces · 629/D

D. 巴巴伊和生日蛋糕

中文机器翻译题面 查看原题

如你所知,每个生日聚会都有蛋糕!这次,巴巴伊要准备非常特别的生日派对蛋糕。

简单的蛋糕是一个具有一定半径和高度的圆柱体。简单蛋糕的体积等于相应圆柱体的体积。 Babaei 有 n 个简单的蛋糕,他将制作一个特殊的蛋糕,将一些圆柱体相互叠放。

但是,还有一些额外的烹饪限制。蛋糕的编号方式使得编号 i 的蛋糕只能放在桌子上或放在编号 j 的蛋糕上,其中 j < i。而且,为了给朋友留下深刻的印象,只有当蛋糕i的体积严格大于蛋糕j的体积时,Babaei才会将蛋糕i放在蛋糕j的上面。

Babaei想要准备一个总体积尽可能大的生日蛋糕。帮助他找到这个价值。

输入

输入的第一行包含一个整数 n (1 ≤ n ≤ 100 000) — Babaei 拥有的简单蛋糕的数量。

以下 n 行每行包含两个整数 ri 和 hi (1 ≤ ri, hi ≤ 10 000),给出第 i 个蛋糕的半径和高度。

输出

打印Babaei可以制作的蛋糕的最大体积。如果您的答案的绝对或相对误差不超过 10 - 6,则视为正确。

即:假设你的答案是a,陪审团的答案是b。如果 $$\frac{|a-b|}{\max(1,b)} \leq 10^{-6}$$,检查程序将认为您的答案正确。

示例

输入 #1

2
100 30
40 10

输出 #1

942477.796077000

输入 #2

4
1 1
9 7
1 4
10 7

输出 #2

3983.539484752

注意

在第一个示例中,最佳方法是选择蛋糕编号 1。

在第二个示例中,获得最大体积的方法是使用索引为 1、2 和 4 的蛋糕。