三分法

HDU3714Error Curves

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
using namespace std;
typedef long long ll;
const int N = 1e4+5;
inline int read() {
    char c=getchar(); int x=0,f=1;
    while(c<'0' || c>'9') {if(c=='-')f=-1; c=getchar();}
    while(c>='0' && c<='9') {x=x*10+c-'0'; c=getchar();}
    return x*f;
}

int n, a[N], b[N], c[N];
double f(double x) {
	double x2 = x*x, ans = a[1]*x2 + b[1]*x + c[1];
	for(int i=2; i<=n; i++) ans = max(ans, a[i]*x2 + b[i]*x + c[i]);
	return ans;
}
void solve() {
	double l=0, r=1000;
	for(int i=0; i<100; i++) {
		double len = (r-l)/3, m1 = l+len, m2 = r-len;
		if(f(m1) < f(m2)) r = m2; 
		else l = m1;
	}
	printf("%.4lf
", f(l));
}
int main() {
	freopen("in", "r", stdin);
	int T = read();
	while(T--) {
		n = read();
		for(int i=1; i<=n; i++) a[i] = read(), b[i] = read(), c[i] = read();
		solve();
	}
}