POJ 1905題目解答－IT工程師數位筆記本

文章出處

POJ 1905題目解答：有一根長len的木棍，加熱了n度，長度會膨脹為len*(1+n*c)，c為膨脹系數。現在把這根木棍夾在兩堵墻之間，木棍會向上彎曲變成弧形，求弧形中點和原木棍中點的高度差。

解題報告

一道典型的二分題目，我們會想到直接二分答案dis，然后就可以計算出這個弧所在的圓的半徑，緊接著就可以求出弧長。用求出的弧長與真正的弧長做對比來確定下一次二分的范圍。

但是有個問題，怎么保證算出的弧長滿足單調性？可以yy一下得到（我蒟蒻，并不會數學嚴格證明:P）。
1.dis小的時候：

2.dis大的時候：

在木棍原長度不變的情況下，dis越大，顯然木棍越膨脹（yy……），所以弧長也就越大，滿足單調性。

滿足了單調性之后，我們就可以安心二分了，這里再詳細說明一下如何求弧長：

根據勾股定理，我們知道(R-dis)^2+(len/2)^2=R^2，所以：
R^2-2*R*dis+dis^2+len^2/4=R^2
2*R*dis=dis^2+len^2/4
R=(dis+len^2/4/dis)/2
根據len’=2*θ*R=2*acos((R-dis)/R)*R（acos表示反三角函數，即知道cos值求角度（弧度制）），就可以得到弧長。
二分的范圍：弧最多是半圓，所以dis最多是len/2。

特殊：當len=0或n=0或C=0時，答案就是0，最好特判掉。否則可能會造成被0除錯誤。

示例程序

#include#includeusing namespace std;const double PI=3.14159265358;double len,n,C,len_; //len為原長度，len_為膨脹后的長度bool check(double dis){    double R=(dis+len*len/4/dis)/2;    return 2*acos((R-dis)/R)*R<=len_; //如果<=len_就驗證成功}int main(){    freopen("program.in","r",stdin);    freopen("program.out","w",stdout);    scanf("%lf%lf%lf",&len,&n,&C);    while (len!=-1||n!=-1||C!=-1)    {        if (!len||!n||!C) {printf("0.000\n");scanf("%lf%lf%lf",&len,&n,&C);continue;} //特判        double L=1e-5,R=len/2,mid;len_=(n*C+1)*len;        while (L<=R)        {            mid=(L+R)/2;            if (check(mid)) L=mid+(1e-5); else R=mid-(1e-5); //驗證成功就大一點，否則小一點        }        printf("%.3f\n",R);        scanf("%lf%lf%lf",&len,&n,&C);    }    return 0;}

看文倉www.kanwencang.com網友整理上傳,為您提供最全的知識大全,期待您的分享，轉載請注明出處。
歡迎轉載：http://www.kanwencang.com/bangong/20170226/107056.html

文章列表