Intro
A geometric problem. Given
\[x = a + 2h\\
y = b + 2h\\
\]
maximize the value of a * b * h (the volume of the box).
This can be done by solving the equation
\[h(x-2h)(y-2h) = 4h^3-2h^2(x+y)+hxy
\]
In this cubic function, the coefficients are:
\[a = 4, b = -2(x+y), c = xy
\]
Formula
Given a, b, and c, we can find the x-value where min/max values happen.
\[q = \frac{-b \pm \sqrt{b^2-3ac}}{3a}
\]
And the value of min / max can be computed by
\[D = aq^3 + bq^2 + cq + d
\]
(d is the constant term in the original cubic function.)
Code
The code is really simple. Use variable a, b, c to represent the coefficients, and finish the computation using the formula in O(1) time for each query.
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
void solve() {
double x, y;
cin >> x >> y;
double a = 4;
double b = -2*(x+y);
double c = x*y;
double q1 = (-b+sqrt(b*b-3*a*c))/3/a;
double q2 = (-b-sqrt(b*b-3*a*c))/3/a;
double ans = 0.0;
if (q1 > 0 && q1 < min(x, y)) ans = max(a*pow(q1,3)+b*pow(q1,2)+c*q1, ans);
if (q2 > 0 && q2 < min(x, y)) ans = max(ans, a*pow(q2,3)+b*pow(q2,2)+c*q2);
cout << fixed << setprecision(12) << ans << '\n';
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin.exceptions(cin.failbit);
int t;
cin >> t;
while (t--) {
solve();
}
}