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

    ACM-POJ EXP 118阅读 0评论

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


    大致题意

    一个1X1的正方形,每条边上有n个不同的点(不包括顶点),并给出它们的坐标。现在把对边相对应的点相连,将正方形分割成(n+1)*(n+1)个小四边形。问最大的四边形的面积是多少。

    解题思路

    计算几何求面积的题,算半条水题吧。。

    基本思路

    构造所有的线段,然后枚举每对水平-竖直线段,求交点,然后计算四边形面积,求最大值。


    应用知识

    ① 叉积(规范相交)

    ② 多边形分解

    ③ 三角形基于计算几何的面积公式(注意正负)


    我先建立一个数学模型说明问题:

    以n=3为例画图 (当然实际上内部的线不一定是正交的,这里只是为了简单说明)

    第一步建立一个大小为 (n+2)*(n+2) 的二维交点矩阵node,每个元素存储一个交点坐标(x,y)

    由于四角交点为定点,每条边上的交点又是输入值,那么外围一圈的交点都是已知了

    由于对边的点是对应相连的,因此要求的就是内部n*n个交点

    显然地,所求的所有交点都是某两条直线规范相交所得,因此就可以直接使用求规范相交的交点的公式,而不需要套用模板了

    交点公式 (及推导过程) 请参看 刘汝佳《算法艺术与信息学竞赛》P357 这里不再说明

    通过两两枚举所有内部直线,就能得到 交点矩阵node[][]


    那么剩下的问题就是求出所有 简单四边形(不包含其他四边形) 的面积,输出最大的一个。那么问题就是:已知一个不规则四边形四个角的坐标,求它的面积

    由于四边形是不规则的,直接求解其面积是非常困难的,唯有将其划分为两个三角形,分别求出两个三角形的面积,再相加

    如图,我求解所有四边形时都是采用如图的划分方法

    那么问题进一步转化为“已知不规则三角形三个角的坐标,如何求其面积”

    不用比较都看得出,计算几何的方法远远优于解析几何,不但省去计算一堆长度的麻烦(避免了精度误差),而且还能利用计算交点时 计算叉积的功能函数cross()

    使用计算几何,不但运算量大大减少了,代码也写少了,结果还更精确

    不过有一点要注意的是,计算几何计算的面积是有方向的,即面积可能为负,所以绝对值必不可少,这点千万注意

    转载请注明:EXP 技术分享博客 » POJ1408 – Fishnet

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

    表情

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

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