记录编号	368557	评测结果	AAAAAAAAAA
题目名称	[USACO Mar08] 土地购买	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	0.091 s
提交时间	2017-02-06 00:45:52	内存使用	2.39 MiB

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
typedef long long LL;
const int MAXN = 50005;
struct field{
  LL x, y;
}a[MAXN], b[MAXN];
bool cmp(field a, field b){
  return a.x < b.x || (a.x == b.x && a.y > b.y);
}
const LL inf = 1ll<<62;
LL f[MAXN], n, m;
int q[MAXN];
int main(){
  freopen("acquire.in", "r", stdin);
  freopen("acquire.out", "w", stdout);
  scanf("%lld", &n);
  for(int i = 1; i <= n; i++)
    scanf("%lld %lld", &b[i].x, &b[i].y); //b是存放原始数据的
  sort(b+1, b+n+1, cmp);
  m = 1; a[1] = b[1];
  for(int i = 2; i <= n; i++){
    while(m && b[i].y > a[m].y)m--; //单调栈
    a[++m] = b[i];
  }
  int h = 1, t = 1;
  for(int i = 1; i <= m; i++){
    while(h < t && a[i].x*(a[q[h]+1].y-a[q[h+1]+1].y) > f[q[h+1]]-f[q[h]])h++;
    f[i] = f[q[h]]+a[q[h]+1].y*a[i].x;
    while(h < t && (f[i]-f[q[t-1]])*(a[q[t]+1].y-a[i+1].y) >= (f[i]-f[q[t]])*(a[q[t-1]+1].y-a[i+1].y))t--;
    q[++t] = i;
  }
  printf("%lld\n", f[m]);
  return 0;
}