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