[日常训练]curves

Description

小 [日常训练]curves 同学的弟弟小昨天学习了数学中的一元二次函数，但是由于学业不精，他一个晚上都在缠着小问一元二次函数的极值问题，小烦不可耐，于是，想请你帮忙弄个程序来应付小。程序要完成以下任务：

给你 [日常训练]curves 个二次函数，记第个为：。

设函数 [日常训练]curves 。

请你求出 [日常训练]curves 的在区间上的最小值，结果保留位有效数字。

Input

输入文件第一行是一个整数 [日常训练]curves 。
接下来行，每行个实数，之间有一个空格分隔。

Output

输出一行一个实数，表示 [日常训练]curves 的在区间上的最小值。

Sample Input

2
3 -2 1
2 -4 2

Sample Output

0.686

HINT

[日常训练]curves

Solution

本题二分 [日常训练]curves 三分都可过.

二分答案,判断 [日常训练]curves 的定义域的交与是否有交集.

画图可知, [日常训练]curves 为单峰函数.三分值,判.

注意精度.

#include<cmath>

#include<ctime>

#include<stack>

#include<queue>

#include<cstdio>

#include<vector>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define eps 1e-10

#define M 1000

#define N 100005

using namespace std;

struct func{

    double a,b,c;

}a[N];

int n;

double l=0.0,r=1000.0,m1,m2;

inline double f(double x){

    double ret=a[1].a*x*x+a[1].b*x+a[1].c;

    for(int i=2;i<=n;++i)

        ret=max(ret,a[i].a*x*x+a[i].b*x+a[i].c);

    return ret;

}

inline void init(){

    scanf("%d",&n);

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

        scanf("%lf%lf%lf",&a[i].a,&a[i].b,&a[i].c);

    while(l+eps<r){

        m1=(r-l)/3.0;m2=l+m1*2.0;m1+=l;

        if(f(m1)>f(m2)) l=m1+eps;

        else r=m2;

    }

    printf("%.3lf\n",f(l));

}

int main(){

    freopen("curves.in","r",stdin);

    freopen("curves.out","w",stdout);

    init();

    fclose(stdin);

    fclose(stdout);

    return 0;

}

秒客网

[日常训练]curves

相关文章