Description
农夫John准备扩大他的农场,他正在考虑N (1 <= N <= 50,000) 块长方形的土地. 每块土地的长宽满足(1 <= 宽 <= 1,000,000; 1 <= 长 <= 1,000,000). 每块土地的价格是它的面积,但FJ可以同时购买多快土地. 这些土地的价格是它们最大的长乘以它们最大的宽, 但是土地的长宽不能交换. 如果FJ买一块3x5的地和一块5x3的地,则他需要付5x5=25. FJ希望买下所有的土地,但是他发现分组来买这些土地可以节省经费. 他需要你帮助他找到最小的经费.
Input
* 第1行: 一个数: N
* 第2..N+1行: 第i+1行包含两个数,分别为第i块土地的长和宽
Output
* 第一行: 最小的可行费用.
Sample Input
4
100 1
15 15
20 5
1 100
Sample Output
500
题目分析：
斜率优化的第一题
题解详见ZTY大佬
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n;
struct your
{
long long x,y;
}a[100000];
bool cmp(your j,your k)
{
if(j.x==k.x) return j.y<k.y;
return j.x<k.x;
}
int tot;
long long f[100000];
int q[100000],l,r;
long long xi(long long i) { return a[i+1].y; }
long long yi(long long i) { return f[i]; }
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%lld%lld",&a[i].x,&a[i].y);
sort(a+1,a+n+1,cmp);
for(int i=1;i<=n;++i)
{
while(tot&&a[tot].y<=a[i].y) tot--;
a[++tot]=a[i];
}
for(int i=1;i<=tot;i++)
{
while(l<r&&yi(q[l+1])-yi(q[l])<a[i].x*(xi(q[l])-xi(q[l+1]))) l++;
f[i]=f[q[l]]+a[q[l]+1].y*a[i].x;
while(l<r&&(yi(i)-yi(q[r]))*(xi(q[r-1])-xi(q[r]))<(yi(q[r])-yi(q[r-1]))*(xi(q[r])-xi(i))) r--;
q[++r]=i;
}
printf("%lld",f[tot]);
return 0;
}
