记录编号	161366	评测结果	AAAAAAAAAA
题目名称	[USACO Mar08] 土地购买	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	0.115 s
提交时间	2015-05-04 21:33:30	内存使用	1.46 MiB

#include<cstdio>
#include<deque>
#include<algorithm>
#include<iostream>
using namespace std;
typedef long long LL;
typedef long double LD;
int n,maxn=0x7fffffff;
class miku 
{
public:
	LL x,y;
	miku(){x=0,y=0;}
}ac[50010];
deque<miku> a;
deque<int> q;
LL f[50010];
bool cmp(miku a,miku b)
{ 
	return a.x<b.x||(a.x==b.x&&a.y>b.y);
}
long double G(int j,int k)
{
	return LD(f[k]-f[j])/LD(a[j+1].y-a[k+1].y);
}
int main()
{
	freopen("acquire.in","r",stdin);
	freopen("acquire.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d",&ac[i].x,&ac[i].y);
		f[i]=maxn;
	}
	sort(ac+1,ac+1+n,cmp);
	a.push_back(ac[1]);
	for(int i=2;i<=n;i++)
	{
		while(!a.empty()&&a[a.size()-1].y<ac[i].y) a.pop_back();
		a.push_back(ac[i]);
	}
	f[0]=0;
	q.push_back(0);
	a.push_front(miku());
	for(int i=1;i<a.size();i++)
	{
		//if(q.size()>2)
		//cout<<G(q[0],q[1])<<endl;
		while(q.size()>1&&G(q[0],q[1])<a[i].x)
			q.pop_front();
			//cout<<"YES"<<endl;
		f[i]=f[q[0]]+a[q[0]+1].y*a[i].x;
		while(q.size()>1&&G(q[q.size()-2],q[q.size()-1])>=G(q[q.size()-2],i))
			q.pop_back();
		//cout<<q.size()<<endl;
		q.push_back(i);
		//cout<<f[i]<<endl;
		//cout<<a[i].x<<" "<<a[i].y<<endl;
	}
	printf("%lld",f[a.size()-1]);
	return 0;
}