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

    ACM-POJ EXP 92阅读 0评论

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


    大致题意

    一只蚂蚁,只会向左转,现在给出平面上很多个点,求解一种走法,

    能使得蚂蚁能经过的点最多,每个顶点该蚂蚁只能经过一次,且所行走的路线不能发生交叉.

    解题思路

    凸包的入门水题,是凸包的一个变形

    网上看到很多人copy别人的,说什么“极坐标排序”,那是Graham Scan Algorithm的做法!虽然Graham只有O(nlogn) ,但是这题完全没必要用它,因为题目的规模很小,我用卷包裹算法照样0 ms 一次AC 。确实理论上卷包裹的O(n^2)不如Graham快,但是规模这么小的题目是反映不出来的。

    Graham能不用就不用,一代码超长超烦,特别是散点集排序。看过算法理论的同学,一般都宁愿用极坐标而不用水平序,但是极坐标排序的比较规则特容易出错。水平排序我没看懂,估计其他菜鸟们也差不多。


    解题的例图题目已经给出,最终的路线就是螺旋形的。要求从 纵坐标 最小的点作为出发点,这个在输入时顺便找出来,可以节省一点点时间= =

    其实无论输入什么样的点集,一定可以走完全部n个点的,这是凸包的性质决定,所以就放手去做了,不用担心走不完的情况

    唯一注意的是,前面提到过时凸包的变形,是因为螺旋线是不封闭的,凸包是封闭的。要想不封闭很简单,做一个标记就可以了,每构造一个凸包顶点,就标记该点,不再与其连线

    当连线完前面n-1个点后,第n个点(最后没被标记的点)就不用再做了,一定是最后一点,输出它就可以了

    其他细节参见我的程序, 卷包裹算法 百度就有了,这里我就不多说了

    转载请注明:EXP 技术分享博客 » POJ1696 – Space Ant

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

    表情

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

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