题目链接：最大四边形面积 题目有配图参考，应该非常好理解。有一个动点 PPP 在笛卡尔坐标系的第一象限内随机在一条函数式为 y=kx+by = kx + by=kx+b 的直线上移动。问这个坐标系原点与动点所能构成的矩形的最大面积是多少。 思路分析 本题可以用暴力三分的解法，也可以使用数学的方法来快速计算答案。关于三分算法的代码和解释在本文的后半部分。 前置知识： 1. 了解并熟悉基本代数函数。 2. 了解一元二次函数。 3. 拥有初中数学基础更好。 如果对一元二次函数不熟悉，可以参考文章：一元二次函数 by 一只姜。 计算矩形的面积比较简单，那就是矩形的底边长乘上矩形的高。很显然，矩形的底边长就是这个动点 PPP 的 xxx 坐标，高就是动点 PPP 的 yyy 坐标。因此矩形的面积应该为 Sarea=x⋅y=x⋅(kx+b)S_{area} = x \cdot y = x \cdot (kx + b)Sarea =x⋅y=x⋅(kx+b)。通过化简可以的得到面积 Sarea=kx2+bxS_{area} = kx^2 + bxSarea =kx2+bx。这是一个一元二次函数 。 很显然，对于这个一元二次函数，这个函数的最大值就是本问题的解。如果这个一元二次函数的开口向下，那么我们就需要求出这个函数的顶点坐标，其中顶点的 yyy 坐标就是答案。但如果这个一元二次函数的开口向上，那么这个矩形的面积就是无限大。 如何判断函数的开口朝向？如果 k>0k > 0k>0 说明这个二次函数开口向上，答案为无穷大。如果 k<0k < 0k<0，说明这个二次函数的开口向下，通过顶点公式可以得到最大值 Sarea=y=4kc−b24kS_{area} = y = \frac{4kc - b^2}{4k}Sarea =y=4k4kc−b2 ，由于 ccc 为 000，进一步化简可得 Sarea=y=−b24kS_{area} = y = \frac{-b^2}{4k}Sarea =y=4k−b2 那么当 kkk 等于 000 的时候呢？这个时候就不是一个一元二次函数了，而是一个线性函数。可以得出结论，这个矩形的面积也是无穷大。 总结 * 如果 k≥0k \ge 0k≥0，输出 −1-1−1。 * 如果 k<0k < 0k<0，输出 −b24k\frac{- b^2}{4k}4k−b2 。 三分算法 三分算法 (Ternary Search) 是一种用于在单峰函数（即函数在一个区间内单调递增，然后单调递减，或者先单调递减然后单调递增）的范围内找到 最大值 或 最小值 的优化方法。它的工作原理于二分搜索类似，但每次将搜索区间分成三部分，而不是两部分。 在二分算法中，我们一般是以区间的中值进行二分。但在三分算法，我们需要将区间分成了三个部分。设当前枚举的区间在 [L,R][L, R][L,R]，那么我们需要选择两个内部点将这个区间分隔开。通常情况下，我们会选择区间的左三分之一和有三分之一作为分割点，坐标分别是为 left_third=L+R−L3left\_third = L + \frac{R - L}{3}left_third=L+3R−L 和 right_third=R−R−L3right\_third = R - \frac{R-L}{3}right_third=R−3R−L 。之后的逻辑与二分类似，每次可以排除左三分之一或者右三分之一（取决于枚举时的实际情况）。最后该算法就可以在对数时间内快速求解。 在这道题中，我们并不直接三分本问题的解，而是计算可以构成最大矩形面积的 PPP 点横坐标。由于 PPP 点只能在第一象限中移动，那么 PPP 点的移动区间应该为 (0,−bk)(0, -\frac{b}{k})(0,−kb )。因此我们用代码枚举这个区间即可。 结论证明 为了验证公式结论的正确性，可以通过分析面积的变化率来证明。为方便起见，在后问中定义 f(x)=S=kx+bf(x) = S = kx + bf(x)=S=kx+b。 首先先根据面积公式可以得到 Sarea=kx2+bxS_{area} = kx^2 + bxSarea =kx2+bx。为了让 SareaS_{area}Sarea 的大小尽可能大，我们需要找到这个函数的 Local Maximum\mathtt{Local \space Maximum}Local Maximum。若一个点满足 Local Maximum\mathtt{Local \space Maximum}Local Maximum 则需要有以下两个前提： 1. f′(x)=dSdx=0f'(x) = \frac{dS}{dx} = 0f′(x)=dxdS =0。 2. f′′(x)=d2Sdx2<0f''(x) = \frac{d^2S}{dx^2} < 0f′′(x)=dx2d2S <0。 计算可得 f′(x)=2kx+bf'(x) = 2kx + bf′(x)=2kx+b，f′′(x)=2kf''(x) = 2kf′′(x)=2k。 因此，只有当 k<0k < 0k<0 的时候才满足条件。其余情况一律输出 −1-1−1 即可。那么对于 k<0k < 0k<0 的时候，我们需要计算 xxx 满足 2kx+b=02kx + b = 02kx+b=0 的解。通过移项可以得出 x=−b2kx = \frac{-b}{2k}x=2k−b 。通过代入 x=−b2kx = \frac{-b}{2k}x=2k−b 到原式可得 Sarea=4kc−b24kS_{area} = \frac{4kc - b^2}{4k}Sarea =4k4kc−b2 ，与上述结论相同。 证毕 Q.E.DQ.E.DQ.E.D。 AC 代码 使用数学方法的 AC 代码如下： 使用三分法的 AC 代码如下：

最大四边形面积-数学法题解 前言 什么！？？你还在为这道最大四边形面积苦恼吗？ 你还在为dalao的Math法看不懂而悲伤吗？ 速速食用这篇题解！Math方法解题超详细(不对处欢迎指正！) 目录 1 解题知识点具备要求 2 题目大意 3 一次函数图像上的分析 (分类讨论) 4 转换二次函数抛物线并求得最值 (重点！！！) 5 代码环节 解题知识点具备 解这道题你需要具备以下知识点 初二：一次函数的图形与性质 y=kx+b(k,b为常数)y=kx+b(k,b为常数)y=kx+b(k,b为常数) 初三：二次函数概念及二次函数(抛物线)的顶点坐标 y=ax2+bx+c(a,b,c为常数)y=ax^2+bx+c(a,b,c为常数)y=ax2+bx+c(a,b,c为常数) 顶点坐标(−b2a,4ac−b24a)(-\frac{b}{2a},\frac{4ac-b^2}{4a})(−2ab ,4a4ac−b2 ) 题目大意 有一条一次函数直线y=kx+by=kx+by=kx+b，已知k和bk和bk和b且直线上有一动点PPP在坐标系的第一象限移动，PPP与数轴构成 矩形PDOCPDOCPDOC(本蒟蒻自定的)，现求S矩形PDOCS_{矩形PDOC}S矩形PDOC 最大，如下图 一次函数图像上的分析 (分类讨论) 通过一次函数的性质我们可以知道 当k>0k>0k>0时，图像的开口是朝上的此时若P在第一象限上移动则解会无限大，如图 但当k<0k<0k<0时，即 题目大意 中图片所示，图像的开口朝下，一次函数图像的第一象限部分是有限制的，所以此时SPDOCS_{PDOC}SPDOC 有最大值 因此明晰了有解和无解的情况 1-当k>0k>0k>0时无解 输出-1 2-当k<0k<0k<0时有解 继续往下求解 转换二次函数抛物线并求得最值 在分析完有无解后，最重要的一步来了，求得最大解 我们依旧拿图片来看 我们设点PPP的横纵坐标上为xpx_pxp 和ypy_pyp ，因为点PPP在一次函数上所以ypy_pyp 满足yp=kxp+by_p=kx_p+byp =kxp +b，所以点PPP可表示为(xp,kxp+b)(x_p,kx_p+b)(xp ,kxp +b) 又因为S矩形PDOC=DP⋅PCS_{矩形PDOC}=DP\cdot PCS矩形PDOC =DP⋅PC且DP=xp,PC=ypDP=x_p,PC=y_pDP=xp ,PC=yp 所以S矩形PDOC=xp⋅yp=xp⋅(kxp+b)=kxp2+bxpS_{矩形PDOC}=x_p\cdot y_p\\=x_p\cdot(kx_p+b)\\=kx_p{^2}+bx_pS矩形PDOC =xp ⋅yp =xp ⋅(kxp +b)=kxp 2+bxp 这样此时S矩形PDOCS_{矩形PDOC}S矩形PDOC 值就变成了一个一元二次方程，求其最大值 求一元二次方程的最大值可以将它抽象为二次函数，继而转为求二次函数(抛物线)的最大值也就是顶点的yyy轴数值，如下图所示 一个二次函数可以表示为y=ax2+bx+c(a,b,c为常数)y=ax^2+bx+c(a,b,c为常数)y=ax2+bx+c(a,b,c为常数) 我们将上面求出的kxp2+bxpkx_p{^2}+bx_pkxp 2+bxp 作观察 发现a=k,b=b,c=0a=k,b=b,c=0a=k,b=b,c=0 而后代入求顶点纵坐标的公式4ac−b24a\frac{4ac-b^2}{4a}4a4ac−b2 因为c=0c=0c=0所以4ac4ac4ac项消掉 最终得出−b24a\frac{-b^2}{4a}4a−b2 所以S矩形PDOC=−b24aS_{矩形PDOC}=\frac{-b^2}{4a}S矩形PDOC =4a−b2 这样我们就把有解情况下的公式求出来了！！！ 代码环节 附带注释！！！

首先，当k=−1k=-1k=−1，即无论怎么移周长都一样的知道怎么做吗？ 那当然是作正方形啊！ 那么，其他的，如Testcase_1呢？ 移动时周长会改变，怎么办呢？ 有了！我们可以复制两份，再拼到一起！ 这样大长方形的周长不管怎么移都不会变了 我们再作正方形就能求出长方形的最大面积了 同理所有长方形的最大面积就可以算了 设当S面积最大时，长方形右边的x坐标值为x 则−kx=kx+b-kx = kx + b−kx=kx+b −2kx=b-2kx=b−2kx=b x=−b2k.x=-\dfrac{b}{2k}.x=−2kb . ∴SABCDmax=x×(kx+b)=x×(−kx)=−b2k×[−k×(−b2k)]=−b24k∴S_{ABCD}max=x×(kx+b)=x×(-kx)=-\dfrac{b}{2k}×[-k×(-\dfrac{b}{2k})]=-\dfrac{b^2}{4k}∴SABCD max=x×(kx+b)=x×(−kx)=−2kb ×[−k×(−2kb )]=−4kb2 . 单个测试点时间复杂度：O(1)O(1)O(1)