解题思路
这题没题解 补一个
算法:三分 / 模拟退火
由于本题更接近三分模板题,所以仅提供三分做法
对于三分的模板总结参考这里
同时呈现三分法证明过程
Code
#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-8; // eps尽量开高,不然会WA
const int N = 100010;
int n, a[N], b[N], c[N];
double check(double x)
{
double res = -1e9;
for (int i = 1; i <= n; i++) res = max(res, a[i] * x * x + b[i] * x + c[i]);
return res;
}
int main()
{
int t; cin >> t;
while (t--)
{
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i] >> b[i] >> c[i];
double l = 0, r = 1000;
while (r - l > eps)
{
double mid = (l + r) / 2;
double mmid = (mid + r) / 2;
if (check(mid) > check(mmid)) l = mid;
else r = mmid;
}
printf("%.4lf\n", check(r));
}
return 0;
}
三“等”分?