Toj 3777 Function Problem

最新推荐文章于 2018-10-06 17:13:32 发布

JohnYu024

最新推荐文章于 2018-10-06 17:13:32 发布

阅读量347

点赞数

文章标签： Toj 三分搜索 Function Problem ACM

本文链接：https://blog.csdn.net/JohnYu024/article/details/78879499

版权

Time Limit: 1.0 Seconds Memory Limit:65536K Special Judge
Total Runs: 437 Accepted Runs:121

Description

We define a function Y = Ax² + Bx +C; (0 ≤ A ≤ 100, 0 ≤ |B| ≤ 5000, |C| ≤ 5000).

Now we have two functions Y₁, Y₂. We define a new function F(x), The value of F(x) is F(x₀) = max(Y₁(x =x₀), Y₂(x = x₀)), whenx = x₀. If you know the value of A, B, C of the two function, calculate the minmum value of F(x₀) (0 ≤x₀ ≤ 1000).

Input

There are multiple test cases, first line is the case number T (T ≤ 100). Every case has two lines, every line has three integers, the value ofA, B, C of the two functions (0 ≤ A ≤ 100, 0 ≤ |B| ≤ 5000, |C| ≤ 5000).

Output

Output a real number on line, Four decimal places reserved.

Sample Input

Sample Output

0.0000
0.5000

Note: Special judge problem, you may get "Wrong Answer" when output in wrong format.

题目大意：给定两个开口向上的二次函数，求对于所有相同的x（0~1000）两个函数中较大的一个的值的最小值。（有点绕，但是应该很容易理解）

解题思路：（一开始以为要用二次函数各种公式，太傻了）正确的解题思路是利用三分搜索，不断缩小范围，找到最小值的一个近似值。

三分搜索类似二分搜索的思想，只是二分只适用于单调函数，而三分适用于凹凸函数。

话不多说，上代码（用的循环而没有使用递归，就这道题来说，递归也ok）：

#include<stdio.h>
#include<iostream>
#include<iomanip>
#include<cmath>
#include<algorithm>
using namespace std;
double a1,b1,c1,a2,b2,c2;
double f(double e){
    return max( a1*e*e+b1*e+c1,a2*e*e+b2*e+c2);
} 
int main(){
	int t;
	cin>>t;
	while(t--){
		cin>>a1>>b1>>c1>>a2>>b2>>c2;
		double left=0,right=1000;
		while(right-left>=1e-8){
			double mid1=left+(right-left)/3,
			       mid2=right-(right-left)/3;
		   if(f(mid1)<f(mid2)+1e-8){
		   	  right=mid2;
		   }
		   else left=mid1;
		}
		cout<<fixed<<setprecision(4)<<f(left)<<endl;
	}
 return 0;
}