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

    ACM-POJ EXP 102阅读 0评论

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


    大致题意

    给定平面上的一些散点集,求最远两点距离的平方值。

    解题思路

    别想着暴力枚举任意亮点距离找最大,行不通,想想三点共线吧!

    平面上的散点集的最远的两点距离必然在这个散点集的凸包的某两个顶点上出现

    那么先求凸包,再枚举顶点距离就OK了。

    别看是3000ms就想用简单的卷包裹,这题数据规模极大,卷包裹铁超(我一开始就是这么做的。。。) 万般无奈不得不用Graham Scan Algorithm。。。。O(nlogn)用来做这题还是相当可观的。


    GrahamScan理解是不困难的,同学们百度搜搜就知道基本思想了:数据结构:栈。而且每个点最多入栈出栈一次。

    问题是用栈构造凸包之前要对散点集进行排序,水平序我不说了,我没看懂,听说很简单。我用的是极坐标排序

    利用叉积的旋向 配合 比较排序 (如插入排序,冒泡,快排等)可以对极坐标排序,推荐用qsort,不要用冒泡之类的,太慢了,用Graham都是想快而已。


    qsort()难点在于 比较规则,(我的程序为cmp函数),必须把“qsort对cmp返回值的处理、cmp返回值、叉积旋向返回值”三者有机结合,否则一定排序出错,详见我的程序,有详细解释。

    Cmp比较规则为“按极角大小逆时针排序,极角相等则近极坐标的点优先”。在网上看到有些童鞋在“极角相同”的情况下,利用第二关键字“距离”计算排序时,是通过计算两点的横坐标到 原点横坐标之差 作为判断“距离”依据。乍一看好像没错,也能AC,其实那是POJ数据库不强大,试试多点与原点的连线垂直于x轴的情况吧!

    最后注意的:在使用qsort之前,必须先找到 散点集中 最左下角的点,把它放在散点集数组的最后一个元素位,作为 极坐标原点(快排的参考点),否则排序也会出错。

    其实只要qsort的cmp函数能处理好了,基本这题就过了,难度不大。

    转载请注明:EXP 技术分享博客 » POJ2187 – Beauty Contest

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

    表情

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

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