Deformed Wheel 滚石头

Posted on 2010-07-01 19:54 王之昊 阅读(549) 评论(0)  编辑 收藏 引用 所属分类: 二分2:30
Deformed Wheel


题意:
给你一个斜面,再给一个凸多边形的石头,让石头从高出放下,沿着斜面滚动,问石头重心最后的位置。因为摩擦力很大,石头不能滑动,只能转动。(还有很多细节,具体见原题)

      首先,这里要确定什么时候石头算稳定了,可以找到石头和斜面相交的两个点,一个是相对石头的最左点A,一个是相对石头的最右点B,这样如果石头要向左转动,必是绕着A转;要向右转动,必是绕着B转。这里有个问题,如果A,B的横坐标相同,那么A取最低的那个,B取最高的那个。
     
      找到A,B两点之后,如果重心G 有 A.x<=G.x <= B.x 那么他是稳定的,如果G.x < A.x 那么他是向左转,如果G.x > B.x那么他是向右转。
     
      其次,要知道石头如果开始转动,不论向左向右,转动多少角度会再次碰到斜面。假设转动theta再次碰到斜面。我们要求出这个theta的值。这里可以采用二分theta的方法来解决,对于某个确定的角度theta1,直接模拟转动theta1角度。看是否超出斜面的范围,如果是,说明theta1大了,否则说明theta1小了。

      二分的实现上我觉得还是有很多trick的,比如
  1. 在检查的时候,要检查石头上是否存在一点是否在斜面的下侧,这里很容易忽视那个支点,如果把支点也一并去检查,很可能因为精度的关系判他在斜面的下方,结果check函数一直都是不合法。
  2. 向左转和向右转的处理上,向左转我采用的是二分[0,PI]转角,向右转我则是二分[-PI, 0]转角,结果写在一起就出问题了,向左转的判定如果在斜面下方,那么是角度大了,向右转的判定如果在斜面下方,实际上是角度小了,尽管绝对值是大了。还有一种写法是枚举[0,PI],在check函数里再判断是向左转,还是向右转。这样不容易写错。


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


posts - 26, comments - 7, trackbacks - 0, articles - 17

Copyright © 王之昊