在一场悲剧的队内训练中习得了新技能——三分法。三分法可以应用于凸函数或者凹函数的求极值。将一个区间分成三段并通过函数值的比较来缩小区间范围,最终就可以求得极值。
#include <cstdio> #include <cstring> #include <algorithm> #include <iostream> #include<climits> #include<string> #include<vector> using namespace std; const int maxn=10005; const double eps=1e-9; double a[maxn],b[maxn],c[maxn]; int n; double f(double x) { double ans=a[0]*x*x+b[0]*x+c[0]; for(int i=1;i<n;i++) { double tem=a[i]*x*x+b[i]*x+c[i]; ans=ans>tem?ans:tem; } return ans; } int main() { int cas; scanf("%d",&cas); while(cas--) { 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(r-l>eps) { double x1=l+(r-l)/3.0,x2=r-(r-l)/3.0; double y1=f(x1),y2=f(x2); if(y1>y2) l=x1; else if(y2>y1) r=x2; else {l=x1;r=x2;} } printf("%.4lf\n",f(r)); } return 0; }