首页 > 代码库 > POJ 1905 Expanding Rods 浮点数二分

POJ 1905 Expanding Rods 浮点数二分

2024-07-05 09:47:13   223人阅读

Expanding Rods
Time Limit: 1000MS Memory Limit: 30000K
Total Submissions: 11145 Accepted: 2879

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.0001
15000 10 0.00006
10 0 0.001
-1 -1 -1

Sample Output

61.329
225.020
0.000

Source

Waterloo local 2004.06.12

题解

又是二分答案的题目。题意是说，一个长为l的细杆会变长，如果固定两个端点，那么这个杆子就会拱起一个圆弧。求圆弧的高度。

如图：


我一开始想的比较简单，直接上手认为是一个可以搞得函数找零点的问题，但是手推函数之后发现一个问题。


对，这个函数是没有极限的，而且在不停地波动中，所以直接去计算零点就容易跪。所以就还是直接模拟去算了。代码挺简单的，主要还是精度问题。

代码示例

/****
	*@author    Shen
	*@title     poj 1905
	*/

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

const double eps = 1e-5;
const double inf = 0xfffffff;
const double PI  = acos(1.0);

double l, n, c, lp;

inline bool test(double x)
{
    double angle = asin(l / x);
    double tmplp = x * angle;
    return tmplp > lp;
}

double Bsearch(double l, double r)
{
    while (r - l > eps)
    {
        double mid = (r + l) * 0.5;
        //printf("%16.4lf%16.4lf%16.4lf\n", l, mid, r);
        if (test(mid)) l = mid;
        else r = mid;
    }
    return r;
}

void solve()
{
    if (n * c < 0.000001)
        printf("0.000\n");
    else
    {
        lp = (1.0 + n * c) * l;
        lp /= 2; l /= 2;//都除二，减少运算
        double r = Bsearch(0.0, inf);
        double h = r - sqrt(r * r - l * l);
        //G++
            printf("%.3f\n", h);
        //C++
        //  printf("%.2lf\n", h);
    }
}

int main()
{
    while (~scanf("%lf%lf%lf", &l, &n, &c))
        if (l < 0) break;
        else solve();
    return 0;
}


联系
我们