Posted on 2010-03-04 23:39
王之昊 阅读(213)
评论(0) 编辑 收藏 引用 所属分类:
pku
这道题很显然不用求凸包, 应为给的两个多边形本身就具有很好的"序".
首先判断两个多边形的凹凸性, 如果两个多边形都是凸的.那么两个凸多边形只会公共一条边,需要检查两端的凹凸性.
如果有凹多边形,那么凹点必定是要和别人耦合的,可以先找一个凹点,再枚举另一个多边形的所有点,看是否和该凹点匹配,如果匹配,就沿着多边形的方向走,继续检查下一对点, 下一对点要么耦合, 要么以一个凸的形状分开.
最后只要检查所有的凹点是否都访问了就可以了.