农夫John准备扩大他的农场,他正在考虑N块长方形的土地. 每块土地的价格是它的面积,但FJ可以同时购买多快土地. 这些土地的价格是它们最大的长乘以它们最大的宽, 但是土地的长宽不能交换. FJ希望买下所有的土地,但是他发现分组来买这些土地可以节省经费. 他需要你帮助他找到最小的经费.

---

首先，我们发现有一些矩形是没有用的！（假如他的x和y都比另一个矩形小）然后我们把它删掉！

我们就得到了x升序，y降序的矩阵序列

显然是dp

n^2的dp：

dp[i]表示买完前i块土地的最小花费

//按x坐标sortfor (int i=1;i<=n;i++)    for (int j=1;j

怎么优化呢？

假如i可以由j和k转移过来，而j状态比k状态优，那么

\(dp[j]+x[i]*y[j+1]<dp[k]+x[i]*y[k+1]\)

移项为\(dp[j]-dp[k]<x[i]*(y[k+1]-y[j+1])\)

再除过去得到\((dp[j]-dp[k])/(y[k+1]-y[j+1])<x[i]\)

然后维护单调队列即可！（如果j比k优，那么k能更新的j都能更新）

#include
    
     #include
     
      #define N 50010typedef long long ll;using namespace std;struct hhh{    ll x,y;    bool operator < (const hhh &b) const    {        if (x==b.x) return y
      
       '9';j=getchar()) if (j=='-') fu=-1;    for (;j>='0' && j<='9';j=getchar()) ans*=10,ans+=j-'0';    return ans*fu;}   double check(ll i,ll j){    return 1.0*(f[j]-f[i])/(y[i+1]-y[j+1]);}int main(){    freopen("buy.in","r",stdin);    freopen("buy.out","w",stdout);    n=read();    for (ll i=1;i<=n;i++) a[i].x=read(),a[i].y=read();    sort(a+1,a+n+1);    for (ll i=1;i<=n;i++)    {        while (tot && a[i].y>=y[tot]) tot--;        x[++tot]=a[i].x;        y[tot]=a[i].y;    }    for (ll i=1;i<=tot;i++)    {        while (l
       
        l && check(q[r],i)