三分 | 函数

【模板】三分 | 函数

题目描述

给定 $n$ 个二次函数 $f_1(x),f_2(x),\dots ,f_n(x)$（均形如 $a{x}^2+bx+c$），设 F ( x ) = max ⁡ { f 1 ( x ) , f 2 ( x ) , . . . , f n ( x ) } F(x)=\max\{f_1(x),f_2(x),...,f_n(x)\} F(x)=max{f1​(x),f2​(x),...,fn​(x)}，求 $F(x)$ 在区间 $[0,1000]$ 上的最小值。

输入格式

输入第一行为正整数 $T$，表示有 $T$ 组数据。

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

输出格式

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

样例 #1

样例输入 #1

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

样例输出 #1

0.0000
0.5000

提示

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

对于 $100\%$ 的数据，$T<10$，$n\le 10^4$，$0\le a\le 100$，$|b|\le 5\times 10^3$，$|c|\le 5\times 10^3$。

Code

// #include <iostream>
// #include <algorithm>
// #include <cstring>
// #include <stack>//栈
// #include <deque>//堆/优先队列
// #include <queue>//队列
// #include <map>//映射
// #include <unordered_map>//哈希表
// #include <aector>//容器，存数组的数，表数组的长度
#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
typedef long long ll;
const ll N=1e4+10;
ll a[N],b[N],c[N];
ll n;

inline double find(double x)
{
	double mx=-1e18;
	for(int i=0;i<n;i++) mx=max(mx,a[i]*x*x+b[i]*x+c[i]);

	return mx;
}

void solve()
{
    cin>>n;

    for(ll i=0;i<n;i++) cin>>a[i]>>b[i]>>c[i];

    double l=0,r=1000;
	while(r-l>1e-9)
    {
		double x=(2*l+r)/3;
		double y=(l+2*r)/3;
		if(find(x)<find(y)) r=y;
		else l=x;	
	}

    printf("%.4lf\n",find(l));
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);

    ll t;
    cin>>t;
    while(t--) solve();
    
    return 0;
}