POJ 1905 Expanding Rods(几何+二分)
http://poj.org/problem?id=1905
题意:
一根两端固定在两面墙上的杆 受热弯曲后变弯曲
求前后两个状态的杆的中点位置的距离. 弯曲后的杆可以看成一个圆的弧,而弯曲前的杆可以看成是该弧的弦.
分析:
假设当前的圆半径为r,且该弧S对应的圆心角为2 θ.h是我们要求的距离.那么我们可以推过上图得到下面3个方程:
(1)θr = 1/2*s (弧/圆周长==弧圆心角/2π)
(2)sinθ= 1/2*L/r (正弦定理)
(3)勾股定理 r^2 – ( r – h)^2 = (1/2*L)^2
那么化简上述公式可得:
那么我们可以通过二分h的长度(h的范围是[0,0.5L],该范围值也不好证明)来计算r的值,然后通过第二个等式来验证r的值是否正确. 如果当前通过h的值算出的r值使得等式(2)右边小于s,那么h值应该更大.
否则L值应该更小.
注意:
二分有个很重要的前提就是单调,本题需要证明等式(2)右边是关于r单调递增的且要证明h与r也是成正比的关系.
下面这个大神把上面的单调关系证明了,还带图解:
http://blog.csdn.net/zhengnanlee/article/details/18494917
AC代码:
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
const double eps=1e-5;
double L,C,n,S;
double get_s(double h)
{
double r= (4*h*h+L*L)/(8*h);
return 2*r*asin(L/(2*r));
}
int main()
{
while(scanf("%lf%lf%lf",&L,&n,&C)==3)
{
if(L<0 && n<0 && C<0) break;
S=(1+n*C)*L;
double low=0,high=L/2;
while(high-low>eps)
{
double mid=(low+high)/2;
if(S>get_s(mid)) low=mid;
else high=mid;
}
printf("%.3lf\n",high);
}
return 0;
}
分享到:
相关推荐
北大POJ1905-Expanding Rods 解题报告+AC代码
西北工业大学POJ试题C++答案代码+课程设计
北大POJ1207-The 3n + 1 problem 解题报告+AC代码
POJ-2870 Light Up + DFS(1级DFS+1级DFS) + Python - 思维导图 链接:https://blog.csdn.net/xxdragon126/article/details/122095922?spm=1001.2014.3001.5501
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
1011,1012,1013,1014,1015,1017,1026,1028,1032,1035,1041,1046,1129 1149 1154 1165 1182 1185 1190 1191 1201 1251 1273 1275 1276 1286 1322 1338 1363 1364 1401 1456 1459 1564 1579 1637 1657 1658 ...
北大POJ初级-计算几何学 解题报告+AC代码
北大POJ初级-简单搜索 解题报告+AC代码
很好很强大的POJ分类 新手+进阶+题目完全分类 赶快下载
北大POJ2031-Building a Space Station【Prim+计算几何】 POJ2031-Building a Space Station【Prim+计算几何】
poj分类poj分类poj分类poj分类
北大POJ3009-Curling 2.0【DFS+Vector+回溯+剪枝】 解题报告+AC代码
poj 1000 - 2000 部分题目 官方分类 poj 1000 - 2000 部分题目 官方分类
poj 百练 题目分类 poj 百练 题目分类
北大POJ3026-Borg Maze【BFS+Prim】 解题报告+AC代码
北大POJ初级-所有题目AC代码+解题报告
北大POJ1159-Palindrome 解题报告+AC代码
北大POJ3733-Changing Digits【DFS+强剪枝】 解题报告+AC代码
北大POJ2002-Squares 解题报告+AC代码
该文档对poj大部分题目进行了分类,有利于喜欢在poj刷题的朋友