303236: CF629D. Babaei and Birthday Cake

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

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 ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF629D/c5d4f85807f95b08a3db7aae534822038a5bf1df.png).

输入输出样例

输入样例 #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 $ .

Input

题意翻译

### 题目描述: 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

加入题单

上一题 下一题 算法标签: