首页 > 代码库 > UVA 1476 - Error Curves(三分法)
UVA 1476 - Error Curves(三分法)
UVA 1476 1476 - Error Curves
题目链接
题意:给几条下凹二次函数曲线,然后问[0,1000]所有位置中,每个位置的值为曲线中最大值的值,问所有位置的最小值是多少
思路:三分法,由于都是下凹函数,所以所有曲线合并起来,仍然是一个下凹函数,满足单峰,用三分求极值
代码:
#include <cstdio> #include <cstring> #include <cmath> #include <algorithm> using namespace std; const int N = 10005; int t, n, ans; struct Line { double a, b, c; } l[N]; double cal(double x) { double ans = l[0].a * x * x + l[0].b * x + l[0].c; for (int i = 1; i < n; i++) ans = max(ans, l[i].a * x * x + l[i].b * x + l[i].c); return ans; } double solve() { double l = 0, r = 1000; while (fabs(l - r) > 1e-9) { double ml = (2 * l + r) / 3; double mr = (l + 2 * r) / 3; if (cal(ml) < cal(mr)) r = mr; else l = ml; } return cal(l); } int main() { scanf("%d", &t); while (t--) { scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%lf%lf%lf", &l[i].a, &l[i].b, &l[i].c); printf("%.4lf\n", solve()); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。