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

    ACM-POJ EXP 108阅读 0评论

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


    大致题意

    给定多边形城堡的n个顶点,绕城堡外面建一个围墙,围住所有点,并且墙与所有点的距离至少为L,求这个墙最小的长度。

    解题思路

    推导公式(1)

    城堡围墙长度最小值 = 城堡顶点坐标构成的散点集的凸包总边长 + 半径为L的圆周长

    由于数据规模较大,必须用GrahamScan Algorithm构造凸包(详细的算法可以参考我的 POJ2187,这里就不再啰嗦了),然后顺序枚举凸包相邻的两点并计算其距离,得到凸包的总边长,最后加上圆周长2πL

    根据圆形的性质,其实就相当于多加了一个r=L的圆,把该圆根据凸包的边数(假设有k条)划分为k段弧,分别用来连接凸包上所有边。这样做的目的就是为了在保证围墙距离城堡至少为L的同时,使得转角处为圆角而不是直角,减少建造围城所需的资源。


    针对上面的公式(1)证明

    证明如下:假如顺时针给出四个点A、B、C、D。组成了凸四边形ABCD。我们不妨过A点作AE垂直于AB,同时过A点再作AF垂直于AD,过B点作BG、BH分别垂直于AB、BC。连结EG,垂线段的长度为L,过A点以AE为半径作一段弧连到AF,同理,使GH成为一段弧。此时EG=AB(边),AB段城墙的最小值为EF+弧EF+弧GH=AB+弧EF+弧GH。对所有点进行同样的操作后,可知城墙的最小值=四边形的周长+相应顶点的弧长(半径都为L)之和。

    下面证明这些顶点弧长组成一个圆。依然以前面的四边形为例。A、B、C、D四顶点各成周角,总和为360*4=1440度,四边形内角和为360度,每个顶点作两条垂线,总角度为4*2*90=720度,所以总圆周角为1440-360-720=360度,刚好组成圆。

    所以四边形ABCD的围墙最短= 四边形的周长+圆周长

    推广到任意多边形,用同样的方法,城墙最短=凸包的周长 + 以L为半径的圆的周长。

    首先,我们得出城墙最短=凸包的周长 + 相应顶点的弧长(半径都为L)之和。

    再证明 相应顶点的弧长(半径都为L)之和=以L为半径的圆的周长。

    事实上,设凸包顶点为n,n个顶点组成n个周角,角度为360*n=2*180*n,凸包的内角和为180*(n-2),作了2*n条垂线,和为2*n*90=180*n,所以总圆周角为2*180*n-180*(n-2)-180*n=360,组成圆。


    转载请注明:EXP 技术分享博客 » POJ1113 – Wall

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

    表情

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

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