ZOJ 3203 3203 Light Bulb【三分法】

版权声明：转载请注明出处。 https://blog.csdn.net/u014427196/article/details/48959865

题目链接： http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=3366

二分法用来解决单调问题，三分法解决凸（凹）函数问题，逼近求解

代码：

#include <iostream>
#include <algorithm>
#include <set>
#include <map>
#include <string.h>
#include <queue>
#include <sstream>
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <string>

using namespace std;

int t;
double H,h,d;

const double EPS = 1e-10;

double calc(double x)
{
    return d-x+H-(H-h)*d/x;
}

double ternarySearch(double low, double high)
{
    double mid, midmid;
    double mid_value;
    double midmid_value;
    while (low + EPS < high)
    {
        mid = (low + high) / 2;
        midmid = (mid + high) / 2;
        mid_value = calc(mid);
        midmid_value = calc(midmid);
        if (mid_value > midmid_value)
            high = midmid;
        else
            low = mid;
    }
    return mid_value;
}

int main()
{
    scanf("%d",&t);
    while (t--)
    {
        scanf("%lf%lf%lf",&H,&h,&d);
        double ans = ternarySearch((H-h)*d/H,d);
        printf("%.3lf\n",ans);
    }
    return 0;
}