Given a point (P) moving along a linear function (y = kx + b) in the first quadrant of a Cartesian plane, determine the maximum area of a rectangle formed by the origin and point (P).

Mathematical Approach

The area (S) of the rectangle is given by: [S = x \cdot y = x(kx + b) = kx^2 + bx] This represents a quadratic function. The solution depends on the coefficient (k):

1. When (k \geq 0): The parabola opens upwards, making the area unbounded. Output (-1).
2. When (k < 0): The parabola opens downwards, with its vertex at: [x = \frac{-b}{2k}] Substituting back gives the maximum area: [S_{\text{max}} = \frac{-b^2}{4k}]

Ternary Search Method

For cases where (k < 0), ternary search can efficiently locate the maximum area by narrowing down the interval ([0, -b/k]). The algorithm proceeds as followss:

1. Divide the interval into three parts using points (L + (R-L)/3) and (R - (R-L)/3).
2. Compare function values at these points to eliminate the left or right third.
3. Repeat until the interval is sufficientyl small.

Implementation

Mathematical Solusion:

#include <iostream>
using namespace std;

int main() {
    int t;
    double k, b;
    cin >> t;
    while (t--) {
        cin >> k >> b;
        if (k >= 0) {
            cout << "-1\n";
            continue;
        }
        double x = -b / (2 * k);
        double max_area = x * (k * x + b);
        printf("%.10lf\n", max_area);
    }
    return 0;
}

Ternary Search Solution:

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

double computeArea(double k, double b, double x) {
    return x * (k * x + b);
}

double ternarySearch(double k, double b) {
    double left = 0, right = -b / k;
    while (right - left > 1e-7) {
        double m1 = left + (right - left) / 3;
        double m2 = right - (right - left) / 3;
        if (computeArea(k, b, m1) > computeArea(k, b, m2))
            right = m2;
        else
            left = m1;
    }
    return computeArea(k, b, (left + right) / 2);
}

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