Vijos - [一本通 1.2 例 3]曲线(三分)

题目链接：https://vijos.org/d/ybttg/p/5c24bbe9f41362c9e1912767 时间限制：1000 ms 内存限制：512 MiB

题目描述

明明做作业的时候遇到了$n$个二次函数$S_i(x)=a{x}^2+bx+c$，他突发奇想设计了一个新的函数$F(x)=\max \{S_i(x)\},i=1\dots n$。 明明现在想求这个函数在$[0,1000]$的最小值，要求精确到小数点后四位，四舍五入。

输入格式

输入包含$T$组数据，每组第一行一个整数$n$；

接下来$n$行，每行$3$个整数$a$,$b$,$c$，用来表示每个二次函数的$3$个系数。注意：二次函数有可能退化成一次。

输出格式

每组数据输出一行，表示新函数$F(x)$的在区间$[0,1000]$上的最小值。精确到小数点后四位，四舍五入。

样例数据

样例输入

2 1 2 0 0 2 2 0 0 2 -4 2

样例输出

0.0000 0.5000

限制与提示

对于$50\%$的数据，$1\le n\le 100$；

对于$100\%$的数据，$1\le T\le 10,1\le n\le 10^5,0\le a\le 100,0\le |b|\le 5000,0\le |c|\le 5000$。

题解

题意：求这个函数$F(x)$在$[0,1000]$的最小值。 思路：利用三分，首先把$l\sim r$这个区间分成三部分($ml$和$mr$)。接下来就是判断，我们因为要求最小值，所以我们要使得左边的值尽可能的小，这样最左边就是最小的。接下来就是找出$ml$和$mr$的$F(x)$，如果$ml$的$F(x)$值小于$mr$的$F(x)$值，那么就将$r$向左边靠近，即$r=mr$，否则$l=ml$。

/* * @Author: lzyws739307453 * @Language: C++ */ #include <bits/stdc++.h> using namespace std; const double eps = 1e-9; const int MAXN = 1e5 + 5; struct ios_in { inline char gc() { static char buf[MAXN], *l, *r; return (l == r) && (r = (l = buf) + fread(buf, 1, MAXN, stdin), l == r) ? EOF : *l++; } template <typename _Tp> inline ios_in & operator >> (_Tp &x) { static char ch, sgn; for (sgn = 0, ch = gc(); !isdigit(ch); ch = gc()) { if (!~ch) return *this; sgn |= ch == '-'; } for (x = 0; isdigit(ch); ch = gc()) x = (x << 1) + (x << 3) + (ch ^ '0'); sgn && (x = -x); return *this; } }Cin; int n, t; int a[MAXN], b[MAXN], c[MAXN]; double Check(double x) { double max_ = -1 / eps; for (int i = 1; i <= n; i++) max_ = max(max_, a[i] * x * x + b[i] * x + c[i]); return max_; } int main() { Cin >> t; while (t--) { Cin >> n; for (int i = 1; i <= n; i++) Cin >> a[i] >> b[i] >> c[i]; double l = 0, r = 1000; while (r - l > eps) { double ml = l + (r - l) / 3; double mr = r - (r - l) / 3; if (Check(ml) < Check(mr)) r = mr; else l = ml; } printf("%.4lf\n", Check(l)); } return 0; }