题目描述

明明做作业的时候遇到了n  个二次函数s_i(x)=ax^2+bx+c ，他突发奇想设计了一个新的函数 f(x)=max{s_i(x)},i=1,2,...,n。

明明现在想求这个函数在 [0,1000] 的最小值，要求精确到小数点后四位，四舍五入。

输入格式

输入包含 t 组数据，每组第一行一个整数n ；

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

输出格式

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

样例

样例输入

2

1

2 0 0

2

2 0 0

2 -4 2

样例输出

0.0000

0.5000

数据范围与提示

对于 50% 的数据，1<=n<=100；

对于 100% 的数据，1<=t<=10,1<=n<=1e5 ,1<=a<=100 ,1<=|b|<=5e3 ,0<=|c|<=5e3 。

___________________________________________

这个题目用到分治中的一种特殊形式，三分。

首先，题目的真正难点在于能够看出：n个函数的最大值构成的新函数仍然是一个开口向上的波谷。

然后就是三分了。三分用来求波谷的最小值（或波峰的最大值）

以求波谷的最小值为例：

求区间[l,r]上的最小值，首先把区间长度等分成三分，分割点为ll和rr

sf=(r-l)/3

ll=l+sf,rr=r-sf;

这样区间就变成了[l,ll,rr,r]四点分成的三份。

然后求ll和rr点对应的函数值，由于是波谷，那么谷底所在点可能有三个可能：

1、在[ll,rr]区间内，由于是波谷，开口向上，那么f[l]>f[ll],f[rr]<f[r]，那么可以去掉[l,ll]和[rr,r]两个区间。

2、在[l,ll]区间内，由于是波谷，开口向上，那么f[ll]<f[rr]<f[r]，那么可以去掉[ll,rr]和[rr,r]两个区间。

3、在[rr,r]区间内，由于是波谷，开口向上，那么f[l]>f[ll]>f[rr]，那么可以去掉[l,ll]和[ll,rr]两个区间。。

那么综合上面三种情况，如果f[ll]>f[rr]，那么谷底可能在中间区[ll,rr]或右侧区[rr,r]，那么左侧[l,rr]去掉;如果f[ll]<f[rr]，那么谷底可能在中间区[ll,rr]或左侧区[l,ll]，那么右侧[rr,r]去掉.

___________________________________________

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 const int maxn=1e5+10;

 4 int a[maxn],b[maxn],c[maxn];

 5 int t,n;

 6 double work(double x)

 7 {

 8     double rt=-1e9;

 9     for(int i=1;i<=n;++i)

10         rt=max(rt,a[i]*x*x+b[i]*x+c[i]);

11     return rt;

12 }

13 int main()

14 {

15     scanf("%d",&t);

16     while(t--)

17     {

18         scanf("%d",&n);

19         for(int i=1;i<=n;++i)

20             scanf("%d%d%d",a+i,b+i,c+i);

21         double l=0,r=1000,ll,rr;

22         while(l+1e-10<r)

23         {

24             double sf=(r-l)/3;

25             ll=l+sf;rr=r-sf;

26             if(work(ll)<work(rr))r=rr;

27             else l=ll;

28         }

29         printf("%.4lf\n",work((l+r)/2));

30     }

31     return 0;

32 }

最新文章

  1. web自动化工具-liveStyle
  2. SpringMVC常用注解的用法
  3. IO复用三种方式
  4. 最小生成树——kruskal算法
  5. android ListView子布局中按钮响应点击事件
  6. BI笔记-SSAS部署的几种方式及部署后的SSAS刷新
  7. Python学习笔记总结1：字符串表示str与repr的用法比较
  8. Python eclipse开发环境搭建
  9. javamail模拟邮箱功能发送电子邮件-基础实战篇（javamail API电子邮件实例）
  10. jQuery骨架
  11. c#异步调用的几种方式
  12. Java开发API文档资源
  13. conda环境复制
  14. PXC快速入门
  15. 微软职位内部推荐-Senior BSP Engineer
  16. Maven根据不同环境打包不同配置文件
  17. 利用c#+jquery+echarts生成统计报表（附源代码）
  18. 在Ubuntu 12.04 桌面上设置启动器（快捷方式）
  19. C# 温故而知新：Stream篇（二）
  20. 树莓派teamviewer远程 windows远程桌面

热门文章

  1. [转载]Mybatis Generator最完整配置详解
  2. CentOS Linux SVN服务器 配置用户目录访问 权限 Authorization failed
  3. jsonp详解及跨域请求
  4. 基于Let&#39;s Encrypt生成免费证书-支持多域名泛域名证书
  5. 单细胞分析实录(2): 使用Cell Ranger得到表达矩阵
  6. .Net Core — 依赖注入
  7. Spark学习进度-实战测试
  8. .NET 云原生架构师训练营（模块二 基础巩固 RabbitMQ 工作队列和交换机）--学习笔记
  9. NP问题/NP完全问题（NP-complete problem）如何判断是否是NP完全问题
  10. 用python做youtube自动化下载器 思路