3410 Split convex polygon

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


最后只要检查所有的凹点是否都访问了就可以了.

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理


posts - 26, comments - 7, trackbacks - 0, articles - 17

Copyright © 王之昊