Posted on 2010-03-04 23:39
王之昊 閱讀(220)
評論(0) 編輯 收藏 引用 所屬分類:
pku
這道題很顯然不用求凸包, 應為給的兩個多邊形本身就具有很好的"序".
首先判斷兩個多邊形的凹凸性, 如果兩個多邊形都是凸的.那么兩個凸多邊形只會公共一條邊,需要檢查兩端的凹凸性.
如果有凹多邊形,那么凹點必定是要和別人耦合的,可以先找一個凹點,再枚舉另一個多邊形的所有點,看是否和該凹點匹配,如果匹配,就沿著多邊形的方向走,繼續檢查下一對點, 下一對點要么耦合, 要么以一個凸的形狀分開.
最后只要檢查所有的凹點是否都訪問了就可以了.