Posted on 2010-07-01 19:54
王之昊 阅读(562)
评论(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的，比如
- 在检查的时候，要检查石头上是否存在一点是否在斜面的下侧，这里很容易忽视那个支点，如果把支点也一并去检查，很可能因为精度的关系判他在斜面的下方，结果check函数一直都是不合法。
- 向左转和向右转的处理上，向左转我采用的是二分［0，PI］转角，向右转我则是二分［-PI， 0］转角，结果写在一起就出问题了，向左转的判定如果在斜面下方，那么是角度大了，向右转的判定如果在斜面下方，实际上是角度小了，尽管绝对值是大了。还有一种写法是枚举［0，PI］，在check函数里再判断是向左转，还是向右转。这样不容易写错。