POJ 1905 - Expanding Rods 【2分/三分】

POJ 1905 - Expanding Rods 【二分/三分】

题目链接：http://poj.org/problem?id=1905

题意：

一根两端固定在两面墙上的杆 受热弯曲后变弯曲

求前后两个状态的杆的中点位置的距离

思路：如图所示，已知s，a 求x。设角度为rad，半径为r， 显然，我们有r = s/ rad = a/sin(rad);即a*rad-s*sin(rad)=0或者rad/sin(rad) = s/a。下面我们就根据这两个式子进行二分或三分。

法一：令函数f(rad) = rad/sin(rad) ，求导找单调性，f'(rad) = (sin(rad)-rad*cos(rad))/sin^2(rad) = cos(rad)/sin^2(rad)*(tan(rad)-rad),rad∈（0,π），故tan(rad)-rad>0;所以函数f(rad) 单调递增。接下来就对函数直接二分吧~

法二：令函数f(rad) = a*rad-s*sin(rad)，目标是求函数的零点，当时我还没有去求导，直接就拿三分上，其实求下 导也是很容易的。下面讲讲我的思路吧。rad∈（0,π）不变，我在没有求导的情况下，也就是说在我还不知道函数的单调性的时候，但是在定义域范围内我知道单调区间最多就是两个，那么这个时候我就直接三分搜索答案了~

最后提醒大家一下，提交的时候注意不要用G++来提交printf("lf")，否则会WA，而C++可以AC，如果要用G++提交，大家不妨用cout<<fixed<<setprecision().....

/**
 *作者：__Xiong
 *日期：2015/7/24
 */
 //法一：二分
#include <cmath>
#include <cstdio>
#include <string>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <algorithm>
using namespace std;
const double eps = 1e-10;
const double PI = 3.1415926535897932384626433832795;
double N,C,L;
int main()
{
    //freopen("input.in","r",stdin);
    while(scanf("%lf%lf%lf",&L,&N,&C)&&N>=0&&C>=0&&L>=0)
    {
        if(N==0||L==0||C==0)
        {
            printf("0.000\n");
            continue;
        }
        double minv = 0,maxv = acos(-1.0), midv;
        double L2 = ( 1 + N * C ) * L;
        while(maxv - minv > 1e-12)
        {
            midv = (minv + maxv) / 2;
            if( 2 * L2 / L > midv / sin(midv / 2))
                minv = midv;
            else    
                maxv = midv;
        }
        //printf("%.3lf\n",L2 / midv * (1-cos(midv / 2)));G++提交不要用prinf("lf")
    }
    return 0;
}
//法二：三分
#include <cmath>
#include <cstdio>
#include <string>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <algorithm>
using namespace std;
const double eps = 1e-10;
const double PI = 3.1415926535897932384626433832795;
double L,C,N,a,s,r,rad,ans;
double Calc(double x) { return fabs(a*x-s*sin(x)); }
void Search() {
    double l,r,mid,midmid,mVal,mmVal;
    l = 0,r = PI/2.0;
    while(r-l>=eps)
    {
        mid = (l+r)/2.0;midmid = (mid+r)/2.0;
        mVal = Calc(mid);mmVal = Calc(midmid);
        if(mVal > mmVal)
        {
            rad = midmid;
            l = mid;
        }
        else if(mVal < mmVal)
        {
            rad = mid;
            r = midmid;
        }
        else
        {
            rad = (mid+midmid)/2.0;
            l = mVal;
            r = mmVal;
        }
    }
    ans = s/rad*(1.0-cos(rad));
    printf("%.3lf\n",ans);//G++提交不要用prinf("lf")
}
int main() {
    //freopen("input.in","r",stdin);
    while(~scanf("%lf %lf %lf",&L,&N,&C))
    {
        if(L<0) break;
        if(N==0||L==0||C==0)
        {
            printf("0.000\n");
            continue;
        }
        s = (1.0+N*C)*L/2.0;
        a = L/2.0;
        Search();
    }
    return 0;
}