题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3714
题意:求n个二次函数在[0,1000]的最小值。
三分枚举。
#include <bits/stdc++.h>
using namespace std; const int maxn = ;
const double eps = 1e-;
double a[maxn], b[maxn], c[maxn];
int n; double f(double x) {
double ret = -;
for(int i = ; i <= n; i++) {
double y = a[i]*x*x+b[i]*x+c[i];
ret = max(ret, y);
}
return ret;
} double ts() {
double lo = , hi = 1000.0;
double ret1, ret2;
while(hi - lo >= eps) {
double mid = (lo + hi) / 2.0;
double mimid = (mid + hi) / 2.0;
ret1 = f(mid);
ret2 = f(mimid);
if(ret1 > ret2) lo = mid;
else hi = mimid;
}
return ret1;
} int main() {
//freopen("in", "r", stdin);
int T;
scanf("%d", &T);
while(T--) {
scanf("%d", &n);
for(int i = ; i <= n; i++) {
scanf("%lf %lf %lf", &a[i], &b[i], &c[i]);
}
printf("%.4lf\n", ts());
}
return ;
}