随着YYHS的OI集训队人数急剧增加，原有的小机房已经容纳不了数量庞大的队员。

于是史老师决定租用一些实验室机位供队员们训练,他正在考虑为N (1 <= N <= 50,000)位队员租用机位。实验室管理员根据要求给出了N个机位的长和宽，每个机位的长宽满足(1 <= 宽 <= 1,000,000; 1 <= 长 <= 1,000,000).

而机位的租用价格是它的面积，实验室管理员也提出，可以同时租用多个机位. 租用这一组机位的价格是它们最大的长乘以它们最大的宽, 但是机位的长宽不能交换. 如果想租下一个3x5的机位和一个5x3的机位,则他需要付5x5=25.

于是问题出现了，史老师希望租下所有的机位,但是他发现分组来租这些机位可以节省经费. 他需要你帮助他找到最小的经费.

* 第1行: 一个数: N

* 第2..N+1行: 每行包含两个数,分别为机位的长和宽

* 第一行: 最小的可行费用.

500

这题如果是用n*n的dp，会超时，所以要用斜率优化，和hdu3669差不多的思路。

#include<iostream>

#include<math.h>

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

#include<vector>

#include<map>

#include<set>

#include<queue>

#include<stack>

#include<string>

#include<algorithm>

using namespace std;

#define ll long long

#define inf 999999999999999999

#define maxn 50050

struct node{

    ll w,h;

}a[maxn],b[maxn];

bool cmp(node a,node b){

    if(a.w==b.w)return a.h>b.h;

    return a.w>b.w;

}

ll dp[maxn];

ll q[1111111];

ll getup(int x)

{

    return dp[x];

}

ll getdown(int x)

{

    return -b[x+1].w;

}

int main()

{

    int n,m,i,j,tot,k;

    while(scanf("%d",&n)!=EOF)

    {

        for(i=1;i<=n;i++){

            scanf("%d%d",&a[i].w,&a[i].h);

        }

        sort(a+1,a+1+n,cmp);

        tot=1;b[tot].w=a[1].w;b[tot].h=a[1].h;

        for(i=2;i<=n;i++){

            if(b[tot].h>=a[i].h)continue;

            tot++;b[tot].w=a[i].w;b[tot].h=a[i].h;

        }

        int front,rear;

        front=1;rear=1;

        q[rear]=0;

        for(i=1;i<=tot;i++){

            //dp[i]=b[1].w*b[i].h;  这里如果前面不把0加入队列的话，那么这句话要加上。

            while(front<rear && getup(q[front+1])-getup(q[front])<=b[i].h*(getdown(q[front+1])-getdown(q[front]) )  ){

                front++;

            }

            k=q[front];

            dp[i]=dp[k]+b[k+1].w*b[i].h;

            //dp[i]=min(dp[i],dp[k]+b[k+1].w*b[i].h);

            while(front<rear && ( getup(q[rear])-getup(q[rear-1] ) )*(getdown(i)-getdown(q[rear] ))>=( getup(i)-getup(q[rear] ) )*(getdown(q[rear])-getdown(q[rear-1] ))   ){

                rear--;

            }

            rear++;

            q[rear]=i;

        }

        printf("%lld\n",dp[tot]);

    }

    return 0;

}