【597】[Usaco2008 Mar]土地购买
【题目描述】
有N (1 <= N <= 50,000) 块长方形的土地. 每块土地的长宽满足(1 <= 宽 <= 1,000,000; 1 <= 长 <= 1,000,000). 每块土地的价格是它的面积,但FJ可以同时购买多快土地. 这些土地的价格是它们最大的长乘以它们最大的宽, 但是土地的长宽不能交换. 如果FJ买一块3×5的地和一块5×3的地,则他需要付5×5=25. FJ希望买下所有的土地,但是他发现分组来买这些土地可以节省经费. 他需要你帮助他找到最小的经费。
【输入格式】
第1行: 一个数: N
第2..N+1行: 第i+1行包含两个数,分别为第i块土地的长和宽。
【输出格式】
求最小的可行费用。
Sample Input
4
100 1
15 15
20 5
1 100
Sample Output
500
HINT
FJ分3组买这些土地: 第一组:100×1, 第二组1×100, 第三组20×5 和 15×15 plot. 每组的价格分别为100,100,300, 总共500
给定一些矩形，分组购买，一组的价格是其中最大的长*最大的宽。
n<=50000
一开始并没有思路。。。
首先，我们考虑没有贡献的矩形——对于x,如果存在a[y]>=a[x] && b[y]>=b[x]，则x是无用的。排序去掉。
排序就先按x排序大到小，再按y排序大到小。
出现排序后x,y,z矩形，x能不能套y但能套z的话，那y也能套z，是不会错的。。
最后一定是a递减，b递增。
so：
f[i]=f[j]+a[j+1]*b[i]
然后用斜率优化。
这个是把除法改成乘法的。
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std; typedef long long LL;
const int N=;
int n,pl,Q[N];
LL l=,r=,ai,xj,bj,j,f[N];
struct node{
LL a,b;
bool bk;
}p[N]; // f[i]=f[j]+a[j+1]*b[i]
// ai=b[i]
// xj=a[j+1]
// bj=f[j] LL XX(int i,int j){return p[i+].a-p[j+].a;}
LL YY(int i,int j){return f[i]-f[j];}
double X(int i){return p[i+].a;}
double Y(int i){return f[i];}
double find_k(int i,int j){return (Y(i)-Y(j))/(X(i)-X(j));} bool cmp(node x,node y){
if(x.a!=y.a) return x.a>y.a;
return x.b>y.b;
} bool judge_1()
{
LL tx=XX(Q[l],Q[l+]),ty=YY(Q[l],Q[l+]);
if(tx>=) return ty>=((-ai)*tx);
return ty<=((-ai)*tx);
} bool judge_2(int i)
{
LL t0=YY(Q[r],Q[r-]),t1=XX(Q[r],Q[r-]),t2=YY(i,Q[r]),t3=XX(i,Q[r]);
if(t1<) t0=-t0,t1=-t1;
if(t3<) t2=-t2,t3=-t3;
return (t0*t3)<(t1*t2);
} int main()
{
freopen("a.in","r",stdin);
// freopen("acquire.in","r",stdin);
// freopen("acquire.out","w",stdout);
scanf("%d",&n);
for(int i=;i<=n;i++)
{
scanf("%lld%lld",&p[i].a,&p[i].b);
p[i].bk=;
}
sort(p+,p++n,cmp);
j=;
for(int i=;i<=n;i++)
{
if(p[i].a<=p[j].a && p[i].b<=p[j].b) p[i].bk=;
else j=i;
}
pl=;
for(int i=;i<=n;i++)
if(p[i].bk) p[++pl]=p[i]; for(int i=;i<=pl;i++)
{
ai=p[i].b;
while(l<r && judge_1()) l++;/*find_k(Q[l],Q[l+1])>=(-ai)*/
j=Q[l];
xj=p[j+].a;
bj=f[j];
f[i]=ai*xj+bj;
while(l<r && judge_2(i)) r--;/*find_k(Q[r],Q[r-1])<find_k(i,Q[r])*/
Q[++r]=i;
}
printf("%lld\n",f[pl]);
return ;
}