• 如果您想对本站表示支持,请随手点击一下广告即可~
  • 本站致力于提供原创、优秀的技术文章~
  • 有任何疑问或建议 均可以在站点右侧栏处 通过各种方式联系站长哦~
  • POJ1905 – Expanding Rods

    ACM-POJ EXP 83阅读 0评论

    全解题报告索引目录 -> 【北大ACM – POJ试题分类


    大致题意

    一根两端固定在两面墙上的杆 受热弯曲后变弯曲

    求前后两个状态的杆的中点位置的距离

    解题思路

    几何二分的混合体

    如图,蓝色为杆弯曲前,长度为L

    红色为杆弯曲后,长度为s

    h是所求


    依题意知

    S=(1+n*C)*L

    又从图中得到三条关系式;

    (1) 角度→弧度公式 θr = 1/2*s

    (2) 三角函数公式 sinθ= 1/2*L/r

    (3) 勾股定理 r^2 – ( r – h)^2 = (1/2*L)^2

    把四条关系式化简可以得到

    逆向思维解二元方程组:

    要求(1)式的h,唯有先求r

    但是由于(2)式是三角函数式,直接求r比较困难

    因此要用顺向思维解方程组

    在h的值的范围内枚举h的值,计算出对应的r,判断这个r得到的(2)式的右边 与 左边的值S的大小关系 ( S= (1+n*C)*L )

    很显然的二分查找了。。。。。


    那么问题只剩下 h 的范围是多少了

    下界自然是0 (不弯曲)

    关键确定上界

    题中提及到

    Input data guarantee that no rod expands by more than one half of its original length.

    意即输入的数据要保证没有一条杆能够延伸超过其初始长度的一半

    就是说 S max = 3/2 L

    理论上把上式代入(1)(2)方程组就能求到h的最小上界,但是实际操作很困难

    因此这里可以做一个范围扩展,把h的上界扩展到 1/2L ,不难证明这个值必定大于h的最小上界,那么h的范围就为 0<=h<1/2L

    这样每次利用下界low和上界high就能得到中间值mid,寻找最优的mid使得(2)式左右两边差值在精度范围之内,那么这个mid就是h


    精度问题是必须注意的

    由于数据都是double,当low无限接近high时, 若二分查找的条件为while(low<high),会很容易陷入死循环,或者在得到要求的精度前就输出了不理想的“最优mid”

    精度的处理方法参考我的程序

    转载请注明:EXP 技术分享博客 » POJ1905 – Expanding Rods

    喜欢 (0) 分享 (0)
    发表我的评论
    取消评论

    表情

    Hi,您需要填写昵称和邮箱!

    • 昵称 (必填)
    • 邮箱 (必填)
    • 网址