[暑假集训Day4T3]曲线
2024-09-04 00:40:06
三分模板。
三分法求单峰函数最优值,之后每次取所有二次函数最优值即可
#pragma GCC optimize(3,"Ofast","inline")
#include<iostream>
#include<cstdio>
#define N 100005
#define eps 1e-9
using namespace std;
int read()
{
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-;ch=getchar();}
return x*f;
}
int t,n;
double ans,a[N],b[N],c[N];
double check(double x)
{
double r=-;
for(int i=;i<=n;i++)
{
r=max(r,double(a[i]*x*x+b[i]*x+c[i]));
}
return r;
}
signed main()
{
//freopen("1.in","r",stdin);
t=read();
while(t--)
{
n=read();
for(int i=;i<=n;i++)
{
a[i]=read();
b[i]=read();
c[i]=read();
}
double l=,r=,lmid,rmid;
while(l+eps<r)
{
rmid=r-(r-l)/3.0;
lmid=l+(r-l)/3.0;
if(check(lmid)<=check(rmid))r=rmid;
else l=lmid;
}
printf("%.4lf\n",check(l));
}
return ;
}
最新文章
- (转)iOS图片拉伸技巧
- Docker 安装及命令
- Android开发中 .9.png格式图形设计:
- 2.前端笔记之css
- 可选的Web Components类库
- vector 的resize 和 reserve
- js获取url及url参数的方法
- CPU卡及NFC供应商
- Delphi XE5 android openurl(转)
- C#_MVC3之使用Authorize简单的验证登录(一)
- matlab使用reshape时按照列优先原则取元素和摆放元素
- codeforces 3D . Least Cost Bracket Sequence 贪心
- CentOS中由一般用户切换为root用户
- mp4文件格式解析
- (转载)java 枚举 循环遍历以及一些简单常见的使用
- [SQL] 函数整理(T-SQL 版)
- Storm入门(十)Twitter Storm: Transactional Topolgoy简介
- python 多线程threading的学习一
- HTML5+CSS3(3)
- 动态SQL1