POJ 1905-Expanding Rods（二分法-中心移動距離）

2019-11-10 17:27:39

字體：大中小

來源：轉載

供稿：網友

Expanding Rods

Time Limit: 1000MS		Memory Limit: 30000K
Total Submissions: 15779		Accepted: 4196

Description

When a thin rod of length L is heated n degrees, it expands to a new length L'=(1+n*C)*L, where C is the coefficient of heat expansion. When a thin rod is mounted on two solid walls and then heated, it expands and takes the shape of a circular segment, the original rod being the chord of the segment. Your task is to compute the distance by which the center of the rod is displaced.

Input

The input contains multiple lines. Each line of input contains three non-negative numbers: the initial lenth of the rod in millimeters, the temperature change in degrees and the coefficient of heat expansion of the material. Input data guarantee that no rod expands by more than one half of its original length. The last line of input contains three negative numbers and it should not be PRocessed.

Output

For each line of input, output one line with the displacement of the center of the rod in millimeters with 3 digits of precision.

Sample Input

1000 100 0.000115000 10 0.0000610 0 0.001-1 -1 -1Sample Output
61.329225.0200.000Source
Waterloo local 2004.06.12題目意思：
有一根棍子受熱會彎曲成一段圓弧，求受熱前后中心的移動距離，也就是圖中的ans。解題思路：
l是原長，ll是受熱彎曲后的長度，補全圓弧所在扇形，半徑為R，根據幾何數學計算公式推導出圖中最下面兩個式子。對ans在[0,0.5*l]的范圍內二分枚舉計算出對應的R值，代入后計算出的值與ll比較：如果大于ll，說明ans大了，改變范圍取前二分之一；反正，說明ans取小了，改變范圍取后二分之一。此外，由于全部是double型，所以要注意比較時的精度。#include<iostream>#include<cstdio>#include<iomanip>#include<cmath>#include<cstdlib>#include<cstring>#include<map>#include<algorithm>using namespace std;#define INF 0xfffffffconst double eps = 1e-8;#define MAXN 50050const double PI = acos(-1.0);int a[MAXN];double l,ll,n,c,r,high,low,mid;int main(){#ifdef ONLINE_JUDGE#else    freopen("F:/cb/read.txt","r",stdin);    //freopen("F:/cb/out.txt","w",stdout);#endif    ios::sync_with_stdio(false);    cin.tie(0);    while(cin>>l>>n>>c)    {        if(l<0&&n<0&&c<0)break;        high=l/2,low=0;        ll=(1+n*c)*l;        while(high-low>eps)        {            mid=(low+high)/2;            r=(4*mid*mid+l*l)/(8*mid);            if(2*r*asin(l/(2*r))<ll)                low=mid;            else                high=mid;        }        cout<<fixed<<setprecision(3)<<mid<<endl;    }    return 0;}/*1000 100 0.000115000 10 0.0000610 0 0.001-1 -1 -1*/