题解
1.首先,\(F(x)\) 图像一定是 下凹的,怎么证明我也不知道,只是感觉是这样
2.既然是下凹的,那么一定有最小值,区间内找极大值/极小值可以用三分
B站有个视频直观地讲解了,一看便知
还有一些小细节,请看讨论区
code
#include <bits/stdc++.h>
using namespace std;
const int N = 1000010;
const double eps=1e-9;
double a[N],b[N],c[N];
int t;
int n;
double get(double mid)
{
double mi=-11451411;
for(int i=1;i<=n;i++) mi=max(mi,a[i]*mid*mid+b[i]*mid+c[i]);
return mi;
}
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%lf%lf%lf",&a[i],&b[i],&c[i]);
double l=0.0000,r=1000.0000,best=-1;
while(r-l>eps)
{
double mid1=l+(r-l)/3.00;
double mid2=r-(r-l)/3.00;
if(get(mid1)<get(mid2)) best=mid1,r=mid2;
else best=mid2,l=mid1;
}
printf("%.4lf\n",get(best));
}
}
标签:const,get,int,double,P1883,mid1,模板,三分
From: https://www.cnblogs.com/pure4knowledge/p/18120091