学步园

http://www.lydsy.com/JudgeOnline/problem.php?id=1597

就是斜率的几何意义

//#define _TEST _TEST
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
/************************************************
Code By willinglive    Blog:http://willinglive.cf
************************************************/
#define rep(i,l,r) for(int i=l,___t=(r);i<=___t;i++)
#define per(i,r,l) for(int i=r,___t=(l);i>=___t;i--)
#define MS(arr,x) memset(arr,x,sizeof(arr))
#define LL long long
#define INE(i,u,e) for(int i=head[u];~i;i=e[i].next)
inline const int getint()
{
    int r=0,k=1;char c=getchar();
    for(;c<'0'||c>'9';c=getchar())if(c=='-')k=-1;
    for(;c>='0'&&c<='9';c=getchar())r=r*10+c-'0';
    return k*r;
}
/////////////////////////////////////////////////
int n,tot;
struct data{LL x,y;}d[50005],a[50005];
LL dp[50005];
int q[50005];
/////////////////////////////////////////////////
bool cmp(data a,data b){return a.x<b.x||a.x==b.x&&a.y<b.y;}
double slope(int x,int y)
{return (double)(dp[y]-dp[x])/(a[x+1].y-a[y+1].y);}
/////////////////////////////////////////////////
void input()
{
    n=getint();
    rep(i,1,n) d[i].x=getint(),d[i].y=getint();
}
void solve()
{
    sort(&d[1],&d[n+1],cmp);
    rep(i,1,n)
    {
    	while(tot&&d[i].y>=a[tot].y)tot--;
    	a[++tot].x=d[i].x; a[tot].y=d[i].y;
    }
    int l=0,r=0;
    rep(i,1,tot)
    {
    	while(l<r&&a[i].x>slope(q[l],q[l+1]))l++;
    	dp[i]=dp[q[l]]+a[q[l]+1].y*a[i].x;
    	while(l<r&&slope(q[r],i)<slope(q[r-1],q[r]))r--;
    	q[++r]=i;
    }
    cout<<dp[tot]<<endl;
}
/////////////////////////////////////////////////
int main()
{
    #ifndef _TEST
    freopen("std.in","r",stdin); freopen("std.out","w",stdout);
    #endif
    input();
    solve();
    return 0;
}