Posted on 2010-07-01 19:54
王之昊 閱讀(593)
評論(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函數里再判斷是向左轉，還是向右轉。這樣不容易寫錯。