D. Babaei and Birthday Cake

题目连接：

Description

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 < 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.

Input

The first line of the input contains a single integer n (1 ≤ n ≤ 100 000) — the number of simple cakes Babaei has.

Each of the following n lines contains two integers ri and hi (1 ≤ ri, hi ≤ 10 000), giving the radius and height of the i-th cake.

Output

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 .

Sample Input

2

100 30

40 10

Sample Output

942477.796077000

Hint

题意

有n个蛋糕，然后第i个蛋糕只能放在地上或者放在体积和编号都比他小的上面

然后问你体积最多能堆多大？

题解：

用线段树维护DP

显然这个东西和lis（最长上升子序列）有一点像

我们首先把每个东西的体积都离散化一下，然后我们选取比他小的最大值，然后进行更新就好了

代码

#include
    
     using namespace std;const int maxn = 1e5+6;typedef double SgTreeDataType;struct treenode{  int L , R  ;  double sum;  int num;  void updata(SgTreeDataType v)  {    sum += v;  }};treenode tree[500000];inline void push_down(int o){}inline void push_up(int o){    tree[o].sum = max(tree[2*o].sum , tree[2*o+1].sum);    if(tree[2*o].sum>tree[2*o+1].sum)        tree[o].num=tree[2*o].num;    else        tree[o].num=tree[2*o+1].num;}inline void build_tree(int L , int R , int o){    tree[o].L = L , tree[o].R = R,tree[o].sum = 0;    tree[o].num = L;    if (R > L)    {        int mid = (L+R) >> 1;        build_tree(L,mid,o*2);        build_tree(mid+1,R,o*2+1);    }}inline void updata2(int QL,int QR,SgTreeDataType v,int o){    int L = tree[o].L , R = tree[o].R;    if (QL <= L && R <= QR)    {        tree[o].sum=max(tree[o].sum,v);    }    else    {        push_down(o);        int mid = (L+R)>>1;        if (QL <= mid) updata2(QL,QR,v,o*2);        if (QR >  mid) updata2(QL,QR,v,o*2+1);        push_up(o);    }}inline SgTreeDataType query(int QL,int QR,int o){    if(QR
     
      >1;        SgTreeDataType res = 0;        if (QL <= mid) res = max(query(QL,QR,2*o),res);        if (QR > mid) res = max(query(QL,QR,2*o+1),res);        push_up(o);        return res;    }}double h[maxn],r[maxn],v[maxn];const double pi = acos(-1.0);vector
      
       V;map
       
         H;int main(){    int n;    scanf("%d",&n);    for(int i=1;i<=n;i++)    {        scanf("%lf%lf",&r[i],&h[i]),v[i]=pi*r[i]*r[i]*h[i];        V.push_back(v[i]);    }    sort(V.begin(),V.end());    V.erase(unique(V.begin(),V.end()),V.end());    for(int i=0;i