本文主要是介绍uva 1476 - Error Curves(三分),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目链接:1476 - Error Curves
题目大意:给定n条二次曲线S(x),定义F(x)=max(Si(x)), 求出F(x)在0~1000上的最小值。
解题思路:数值方法,三分。
#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;
const int maxn = 10005;int n, a[maxn], b[maxn], c[maxn];double f (double x) {double ret = a[0] * x * x + b[0] * x + c[0];for (int i = 0; i < n; i++)ret = max(ret, a[i] * x * x + b[i] * x + c[i]);return ret;
}double search (double l, double r) {for (int i = 0; i < 100; i++) {double p = l + (r-l) / 3;double q = r - (r-l) / 3;if (f(p) > f(q))l = p;elser = q;}return l;
}int main () {int cas;scanf("%d", &cas);while (cas--) {scanf("%d", &n);for (int i = 0; i < n; i++)scanf("%d%d%d", &a[i], &b[i], &c[i]);double x = search(0, 1000);printf("%.4lf\n", f(x));}return 0;
}
这篇关于uva 1476 - Error Curves(三分)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!