三分 HDOJ 3714 Error Curves

题目传送门

 /*
三分:凹(凸)函数求极值
*/
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std; const int MAXN = 1e4 + ;
const int INF = 0x3f3f3f3f;
const double EPS = 0.0000000001;
struct F {
double a, b, c;
}f[MAXN];
int n; double cal(double x) {
double res = -INF;
for (int i=; i<=n; ++i) {
res = max (res, f[i].a * x * x + f[i].b * x + f[i].c);
}
return res;
} int main(void) { //HDOJ 3714 Error Curves
//freopen ("HDOJ_3714.in", "r", stdin); int T; scanf ("%d", &T);
while (T--) {
scanf ("%d", &n);
for (int i=; i<=n; ++i) {
scanf ("%lf%lf%lf", &f[i].a, &f[i].b, &f[i].c);
} double l = 0.0, r = 1000.0;
for (int i=; i<=; ++i) {
double mid = (l + r) / ;
double rmid = (mid + r) / ;
if (cal (mid) < cal (rmid)) r = rmid;
else l = mid;
}
printf ("%.4f\n", cal (r));
} return ;
}
上一篇:UVALive 5009 Error Curves 三分


下一篇:Error Curves(2010成都现场赛题)