最大四边形面积｜三分算法&数学解法

题目链接：最大四边形面积

题目有配图参考，应该非常好理解。有一个动点 $P$ 在笛卡尔坐标系的第一象限内随机在一条函数式为 $y = kx + b$ 的直线上移动。问这个坐标系原点与动点所能构成的矩形的最大面积是多少。

思路分析

本题可以用暴力三分的解法，也可以使用数学的方法来快速计算答案。关于三分算法的代码和解释在本文的后半部分。

前置知识：

1. 了解并熟悉基本代数函数。
2. 了解一元二次函数。
3. 拥有初中数学基础更好。

如果对一元二次函数不熟悉，可以参考文章：一元二次函数 by 一只姜。

计算矩形的面积比较简单，那就是矩形的底边长乘上矩形的高。很显然，矩形的底边长就是这个动点 $P$ 的 $x$ 坐标，高就是动点 $P$ 的 $y$ 坐标。因此矩形的面积应该为 $S_{area} = x \cdot y = x \cdot (kx + b)$。通过化简可以的得到面积 $S_{area} = kx^2 + bx$。这是一个一元二次函数 。

很显然，对于这个一元二次函数，这个函数的最大值就是本问题的解。如果这个一元二次函数的开口向下，那么我们就需要求出这个函数的顶点坐标，其中顶点的 $y$ 坐标就是答案。但如果这个一元二次函数的开口向上，那么这个矩形的面积就是无限大。

如何判断函数的开口朝向？如果 $k > 0$ 说明这个二次函数开口向上，答案为无穷大。如果 $k < 0$，说明这个二次函数的开口向下，通过顶点公式可以得到最大值 $S_{area} = y = \frac{4kc - b^2}{4k}$，由于 $c$ 为 $0$，进一步化简可得 $S_{area} = y = \frac{-b^2}{4k}$

那么当 $k$ 等于 $0$ 的时候呢？这个时候就不是一个一元二次函数了，而是一个线性函数。可以得出结论，这个矩形的面积也是无穷大。

总结

• 如果 $k \ge 0$，输出 $-1$。
• 如果 $k < 0$，输出 $\frac{- b^2}{4k}$。

三分算法

三分算法 (Ternary Search) 是一种用于在单峰函数（即函数在一个区间内单调递增，然后单调递减，或者先单调递减然后单调递增）的范围内找到 最大值 或 最小值 的优化方法。它的工作原理于二分搜索类似，但每次将搜索区间分成三部分，而不是两部分。

在二分算法中，我们一般是以区间的中值进行二分。但在三分算法，我们需要将区间分成了三个部分。设当前枚举的区间在 $[L, R]$，那么我们需要选择两个内部点将这个区间分隔开。通常情况下，我们会选择区间的左三分之一和有三分之一作为分割点，坐标分别是为 $left\_third = L + \frac{R - L}{3}$ 和 $right\_third = R - \frac{R-L}{3}$。之后的逻辑与二分类似，每次可以排除左三分之一或者右三分之一（取决于枚举时的实际情况）。最后该算法就可以在对数时间内快速求解。

在这道题中，我们并不直接三分本问题的解，而是计算可以构成最大矩形面积的 $P$ 点横坐标。由于 $P$ 点只能在第一象限中移动，那么 $P$ 点的移动区间应该为 $(0, -\frac{b}{k})$。因此我们用代码枚举这个区间即可。

结论证明

为了验证公式结论的正确性，可以通过分析面积的变化率来证明。为方便起见，在后问中定义 $f(x) = S = kx + b$。

首先先根据面积公式可以得到 $S_{area} = kx^2 + bx$。为了让 $S_{area}$ 的大小尽可能大，我们需要找到这个函数的 $\mathtt{Local \space Maximum}$。若一个点满足 $\mathtt{Local \space Maximum}$ 则需要有以下两个前提：

1. $f'(x) = \frac{dS}{dx} = 0$。
2. $f''(x) = \frac{d^2S}{dx^2} < 0$。

计算可得 $f'(x) = 2kx + b$，$f''(x) = 2k$。

因此，只有当 $k < 0$ 的时候才满足条件。其余情况一律输出 $-1$ 即可。那么对于 $k < 0$ 的时候，我们需要计算 $x$ 满足 $2kx + b = 0$ 的解。通过移项可以得出 $x = \frac{-b}{2k}$。通过代入 $x = \frac{-b}{2k}$ 到原式可得 $S_{area} = \frac{4kc - b^2}{4k}$，与上述结论相同。

证毕 $Q.E.D$。

AC 代码

使用数学方法的 AC 代码如下：

#include <iostream>
#include <algorithm>
#define int long long
using namespace std;

int t;
double a, b;

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> t;
    while(t--){
        cin >> a >> b;
        if (a >= 0) {
            printf("-1\n");
            continue;
        }
        double x = (b * (-1)) / (2 * a);
        double ans = x * (a * x + b);
        printf("%.10lf\n", ans);
    }
    return 0;
}

使用三分法的 AC 代码如下：

#include <iostream>
#include <cmath>
#include <limits>
using namespace std;

int t; double k, b;

// 计算正方形面积
double area(double k, double b, double x) {
    return x * (k * x + b);
}

// 三分法
double ternarySearch(double k, double b) {
    double left = 0;
    
    // 与x轴的交点横坐标。
    double right = -b / k; 
    while (right - left > 1e-7) {
        double leftThird = left + (right - left) / 3;
        double rightThird = right - (right - left) / 3;
        
        if (area(k, b, leftThird) > area(k, b, rightThird)) 
            right = rightThird;
        else left = leftThird;
    }
    
    return area(k, b, (left + right) / 2);
}

int main() {
    cin >> t; 
    while (t--) {
        cin >> k >> b;
        if (k >= 0) cout << -1 << endl; 
        else {
            double maxArea = ternarySearch(k, b);
            printf("%.6lf\n", maxArea);
        }
    }
    return 0;
}