斜率优化DP的综合运用，对斜率优化的新理解。
详细介绍见『玩具装箱TOY 斜率优化DP』
Farmer John is considering buying more land for the farm and has his eye on N (1 <= N <= 50,000) additional rectangular plots, each with integer dimensions (1 <= width_i <= 1,000,000; 1 <= length_i <= 1,000,000).
If FJ wants to buy a single piece of land, the cost is $1/square unit, but savings are available for large purchases. He can buy any number of plots of land for a price in dollars that is the width of the widest plot times the length of the longest plot. Of course, land plots cannot be rotated, i.e., if Farmer John buys a 3x5 plot and a 5x3 plot in a group, he will pay 5x5=25.
FJ wants to grow his farm as much as possible and desires all the plots of land. Being both clever and frugal, it dawns on him that he can purchase the land in successive groups, cleverly minimizing the total cost by grouping various plots that have advantageous width or length values.
Given the number of plots for sale and the dimensions of each, determine the minimum amount for which Farmer John can purchase all
约翰准备扩大他的农场，眼前他正在考虑购买N块长方形的土地。如果约翰单买一块土 地，价格就是土地的面积。但他可以选择并购一组土地，并购的价格为这些土地中最大的长 乘以最大的宽。比如约翰并购一块3 × 5和一块5 × 3的土地，他只需要支付5 × 5 = 25元， 比单买合算。 约翰希望买下所有的土地。他发现，将这些土地分成不同的小组来并购可以节省经费。 给定每份土地的尺寸，请你帮助他计算购买所有土地所需的最小费用。
Input FormatLine 1: A single integer: N
Lines 2..N+1: Line i+1 describes plot i with two space-separated integers: width_i and length_i
Output FormatLine 1: The minimum amount necessary to buy all the plots.
Sample Input 4 100 1 15 15 20 5 1 100 Sample Output 500 解析这是一道\(USACO\)的题，相比之前的玩具装箱，难度较大，我们通过这道题来更透彻地理解斜率优化\(DP\)。
显然，这不是一道明显的\(DP\)题，我们需要先做一些转换。有一个很明显的贪心，如果一块土地\(P\)的长和宽都大于另一块土地\(Q\)的话，那么显然\(Q\)我们是可以无视的，应为我们在购买\(P\)时，可以顺便购买\(Q\)，不会带来任何额外的花费。
为了建立合适的\(DP\)模型，我们先要处理题面中的一些其他的问题。
这里我们使用栈来解决无用土地这个问题。
先将所有土地存入一个结构体中，然后就可以以长度\(l\)为第一关键字，宽度\(w\)为第二关键字对土地进行排序。排序完成后，我们需要将土地一一加入栈。
在加入一块土地时，我们需要检查:栈顶的土地的宽度是否小于等于这块土地的宽度，由排序可知，栈顶的土地的长度一定小于等于这块土地的长度，如果栈顶的土地的宽度也小于等于这块土地的宽度的话，我们就可以判定当前栈顶的土地是一块无用土地。那么，可以将栈顶土地直接弹出。
最后，栈中剩下的土地就是有效的土地。我们将其重新取出，并重新以长度\(l\)为第一关键字，宽度\(w\)为第二关键字对土地进行排序。
在处理完其他问题后，我们需要建立朴素\(DP\)模型。
这时候，如果我们将所得的有效土地视为一个个矩形，排序后，放在平面直角坐标系中应满足：长度\(x\)随着下标的增大而增大，高度\(y\)随着下标的增大而减小，如下图所示。
设\(f_i\)代表购买了前i块土地的最小花费，利用排序后的性质，那么我们就可以建立状态转移方程:
\[ f_i=\min_{j<i}\{y_{j+1}x_i+f_j\} \] STEP 3: 建立斜率函数
得到了\(DP\)方程后，观察得知，方程形如\(f_i=min/max\{a_i+b_j+kc_id_j+f_j\}\)，即:方程中除了含有\(f_j\)以及单独和\(i,j\)有关的项外，还含有既和i有关，又和j有关的项。对于这种方程，我们考虑斜率优化。首先，我们需要利用状态转移方程建立斜率函数。
加入我们找到了最优的\(f_j\)，那么由方程可得:
\[
f_i=y_{j+1}x_i+f_j
\\⇒f_j=-y_{j+1}x_i+f_i
\]
通常，我们视\(f_j\)为\(y\)，既和\(i\)有关，又和\(j\)有关的项中，视和\(i\)有关的部分为\(k\)，和\(j\)有关的部分为\(x\)，方程中的其余项为\(b\)。那么就可以得到斜率函数\(y=kx+b\)。
这里，出现了一种特殊情况:既和\(i\)有关，又和\(j\)有关的项是负数，那么我们通常将负号看做是与\(y\)有关的项的。
那么结果就是:视\(f_j\)为\(y\)，视\(-y_{j+1}\)为\(x\)，视\(x_i\)为\(k\)，视\(f_i\)为\(b\)，得到\(y=kx+b\)。
得到斜率函数后，我们需要通过图像分析其性质，完成代码实现。
首先，我们得出函数的性质:
1.过定点\(P_j(-y_{j+1},f_j)\)
2.斜率为\(x_i\)