LightOJ1137Expanding Rods (数学公式推导加二分法的应用)
Expanding Rods
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. That means you have to calculate h as in the picture.
Input
Input starts with an integer T (≤ 20), denoting the number of test cases.
Each case contains three non-negative real numbers: the initial length of the rod in millimeters L, the temperature change in degrees n and the coefficient of heat expansion of the material C. Input data guarantee that no rod expands by more than one half of its original length. All the numbers will be between 0 and 1000 and there can be at most 5 digits after the decimal point.
Output
For each case, print the case number and the displacement of the center of the rod in single line. Errors less than 10-6 will be ignored.
Sample Input
3
1000 100 0.0001
150 10 0.00006
10 0 0.001
Sample Output
Case 1: 61.3289915
Case 2: 2.2502024857
Case 3: 0
题意:
讲来讲去,还是老套路,先讲一下这道题的意思是什么,这道题实际上是讲了一个弓形,知道了他的弦长和弧长,也就是怎么求高的问题,其实求高,本道题的背景就是一个有原长为L的钢条,经过热胀冷缩以后变成了弓形的形状,他的温度变化是n度,然后热膨胀系数为C,膨胀后的钢条的弦长为L',计算公式为: L' = (1+n*C)*L,好了,题意也讲的差不多了,接下来讲思路。
思路:
这道题目的思路其实真的非常简单,如果从数学来说的话估计牛逼的很快就搞定,但从计算机来看的话,主要是要控制好精度,这个比较麻烦,所以干脆用二分法来解决,so easy。就是把长度进行了二分,然后由数学公式得到两个式子:由勾股定理可得,此为我们要用到的公式。这样只要把其中一个作为while(right-left>1e-6)的结论,也就是说我们实际上连圆弧的半径都是不知道的,然后就是把这个公式作为定理写出来,然后再将if(r*2*(asin(l/2/r))<L)作为二分的判断条件即可。
来来来,盗张图,把队友的图盗来了:
这个图非常的形象的解释了几何关系:
好,接下来正式上代码:
#include<bits/stdc++.h>
using namespace std;
int main()
{
double l,n,c,L;//l表示原长,n表示加热n度,c表示热膨胀系数,L表示膨胀以后的长度
int t;//表示测试次数
scanf("%d",&t);
while(t--)
{
double left,mid,right,r,num;//其实这样的话就是把所求的弓形的高度看成是一个区间,然后left表示区间左端点,right表示区间右端点
scanf("%lf %lf %lf",&l,&n,&c);//然后输入原长,加热的几度,热膨胀系数
left=0;
right=l/2;//将区间缩小,很容易看出高度一定没有L的一半,使计算量更加小
while(right-left>1e-6)//注意,这一步一定要有一个精度控制 ,当小于这个临界值的时候便停止循环,
{
mid=(left+right)/2;//将高度进一步缩小带入下面的两个式子中进行比较
r=l*l/8/mid+mid/2;//第一个式子当作定理
if(r*2*(asin(l/2/r))<L)//第二个式子当作条件进行判断
{
left=mid;
}
else
{
right=mid;
}
}
printf("Case %d: ",++num);
printf("%.6f\n",mid); //输出 mid left right 均可
}
}
这道题二分的思路还是非常的简单的,大家可以自己重新推导下公式,做的话应该也快的。
上一篇: LeetCode刷题笔记——股票价格跨度
下一篇: 解惑内网无法上网的故障