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函數里再判斷是向左轉,還是向右轉。這樣不容易寫錯。