题目链接: https://vjudge.net/contest/537370#problem/H

题意

给出 t 组数据，对于每一组数据，给出 n 个一元二次方程 fi(x)=ax+bx+c 的系数 a, b, c，得到一个新的曲线 g(x) = max{sigma(fi(x))}，求 g(x) 的最小值。

(T < 100) (n ≤ 10000) (0 ≤ a ≤ 100), (|b| ≤ 5000), (|c| ≤ 5000), 0 ≤ x ≤ 1000

思路

简单画个图分析一下可以得到新曲线 g(x) 也是一条与一元二次方程类似的先单调下降后单调上升的曲线。

然后就可以三分这个最低点。

复杂度 O(log(1000/eps))。

代码

#include <cstdio>
#include <vector>

#define NL putchar(10);

const int maxN = 2e5;
const double eps = 1e-15;

int n; double a[maxN], b[maxN], c[maxN];

double check(double x) {
  double max; bool fst = 1;
  for(int i = 0; i < n; ++i) {
    const double cur = (a[i]*x*x+b[i]*x+c[i]);
    max = fst ? (fst=0,cur) : max > cur ? max : cur;
  }
  return max;
}

int main() {
  int t; scanf("%d", &t);
  while(t--) {
    scanf("%d", &n);
    for(int i = 0; i < n; ++i) { scanf("%lf%lf%lf", a+i, b+i, c+i); }
    double l = 0.0, r = 1000.0;
    while(l < r-eps) {
      const double m1 = l+(r-l)/3.0, m2 = l+2*(r-l)/3.0;
      const double y1 = check(m1), y2 = check(m2);
      if (y1 > y2) { l = m1; }
      else { r = m2; }
    }
    printf("%.4f", check(r)); NL;
  }
  return 0;
}