• 如果您想对本站表示支持,请随手点击一下广告即可~
  • 本站致力于提供原创、优秀的技术文章~
  • 有任何疑问或建议 均可以在站点右侧栏处 通过各种方式联系站长哦~
  • POJ1584 – A Round Peg in a Ground Hole

    ACM-POJ EXP 157阅读 0评论

    全解题报告索引目录 -> 【北大ACM – POJ试题分类


    大致题意

    按照顺时针或逆时针方向输入一个n边形的顶点坐标集,先判断这个n边形是否为凸包

    再给定一个圆形(圆心坐标和半径),判断这个圆是否完全在n变形内部

    解题思路

    题意已经很直白了。。就是那个思路。。。

    注意输入完顶点集后,要封闭多边形,方便后面枚举边。

    封闭方法

    定义点集数组Vectex[1~n]记录n个顶点,再令Vectex[0]=Vectex[n],Vectex[n+1]=Vectex[1]


    1、判断凸包

    由于点集已经按某个时针方向有序,因此可以先定义一个方向系数direction=0

    两两枚举n边形的边,用叉积判断这两条边的转向(右螺旋或左螺旋),由于存在散点共线的情况,因此当且仅当叉积的值temp第一次不为0时,direction=temp,direction的值此后不再改变。(direction>0 则为右螺旋逆时针,direction<0则为左螺旋顺时针)

    此后继续枚举剩下的边,只要判断direction*temp>=0即可,当存在一个direction*temp<0的边,说明这是凹多边形,就不是凸包了。

    2、判断圆心与多边形的关系

    用环顾法

    设圆心为P,逐条枚举n边形的边AB,利用

    计算PA和PB的夹角,最后求和得到的就是环顾角。

    (1) 圆心在多边形内部时,环顾角=±360

    (2) 圆心在多边形外部时,环顾角=0

    (3) 圆心在多边形边上时(不包括顶点),环顾角=±180

    (4) 圆心在多边形顶点时,环顾角为(0,360)之间的任意角,其实就是圆心所在的顶点的两条邻接边的夹角。

    3、当圆心在圆内时,判断圆与多边形的关系

    设圆心为P,逐条枚举n边形的边AB,利用 S=0.5 * ( PA x PB ) 得到△PAB的面积,

    再根据公式S=0.5*|AB|*h,可以得到

    枚举所有h与圆的半径R比对,只要所有的边都有R-h>=0,则说明圆在多边形内

    Source修正

    Mid-Atlantic 2003 (问题D)

    测试数据

    本文第二页附带测试数据

    测试数据下载


    转载请注明:EXP 技术分享博客 » POJ1584 – A Round Peg in a Ground Hole

    喜欢 (0) 分享 (0)
    发表我的评论
    取消评论

    表情

    Hi,您需要填写昵称和邮箱!

    • 昵称 (必填)
    • 邮箱 (必填)
    • 网址