Babaei and Birthday Cake

题意翻译

### 题目描述： Babaei打算制作一个特殊的蛋糕。蛋糕由一些已知半径和高度的圆柱体组成，蛋糕的体积等于相应圆柱体的体积之和。 但是，还有一些额外的烹饪限制。编号为 i 的蛋糕只能放在桌子上或编号为 j 的蛋糕上，其中j < i。 此外，为了给朋友们留下深刻印象，只有当蛋糕 i 的体积超过蛋糕 j 的体积时，Babaei才会把蛋糕 i 放在蛋糕 j 上面。 Babaei想要准备一个总体积最大的生日蛋糕，请你帮助他找到这个最大体积。 ### 输入格式： 输入的第一行包含一个整数 n（1 <= n <= 100000）代表 Babaei的蛋糕数量。 以下n行中的每一行包含两个整数ri和hi（1 <= ri，hi <= 10000），代表第 i 个蛋糕的半径和高度。 ### 输出格式： 输出Babaei可以制作的蛋糕的最大体积。如果误差不超过1e-6，则该答案将被视为正确。即：输出为a，标准答案为b，若|a-b|/max(1,b)≤1e-6，你可以AC

题目描述

As you know, every birthday party has a cake! This time, Babaei is going to prepare the very special birthday party's cake. Simple cake is a cylinder of some radius and height. The volume of the simple cake is equal to the volume of corresponding cylinder. Babaei has $ n $ simple cakes and he is going to make a special cake placing some cylinders on each other. However, there are some additional culinary restrictions. The cakes are numbered in such a way that the cake number $ i $ can be placed only on the table or on some cake number $ j $ where $ j&lt;i $ . Moreover, in order to impress friends Babaei will put the cake $ i $ on top of the cake $ j $ only if the volume of the cake $ i $ is strictly greater than the volume of the cake $ j $ . Babaei wants to prepare a birthday cake that has a maximum possible total volume. Help him find this value.

输入输出格式

输入格式

The first line of the input contains a single integer $ n $ ( $ 1<=n<=100000) $ — the number of simple cakes Babaei has. Each of the following $ n $ lines contains two integers $ r_{i} $ and $ h_{i} $ ( $ 1<=r_{i},h_{i}<=10000 $ ), giving the radius and height of the $ i $ -th cake.

输出格式

Print the maximum volume of the cake that Babaei can make. Your answer will be considered correct if its absolute or relative error does not exceed $ 10^{-6} $ . Namely: let's assume that your answer is $ a $ , and the answer of the jury is $ b $ . The checker program will consider your answer correct, if .

输入输出样例

输入样例 #1

2
100 30
40 10

输出样例 #1

942477.796077000

输入样例 #2

4
1 1
9 7
1 4
10 7

输出样例 #2

3983.539484752

说明

In first sample, the optimal way is to choose the cake number $ 1 $ . In second sample, the way to get the maximum volume is to use cakes with indices $ 1 $ , $ 2 $ and $ 4 $ .