ACM:给定点集S,求S中周长最小的三角形（点集中点数N

来源：学生作业帮编辑：作业帮分类：数学作业时间：2024/05/24 08:17:18

用分治就可以过了.楼主可以参考一下最近点对问题的算法：
算法如下：先将所有的点按x坐标排序,然后每次分成左右两个部分,分别递归求解这两个点集中的最小周长.最后考虑跨越这两个点集的3个点的最小周长,用当前求得的最优解可以缩小枚举的范围.
再问：先算分治算出出左右两个点集的最小周长min,然后将中位线两边距离中位线不大于(min/2)的点加入中间枚举范围，这样做可以么，主要想问下枚举的部分怎么做
再答：将这些点按y坐标排序，然后在这堆点里面枚举三角形的3个顶点，枚举的时候保证3个点的x,y坐标差不超过 |min/2|，这样就可以把枚举量控制在很小的范围以内了。思想和最近点对问题几乎是完全一样的。核心算法如下： minimum_perimeter(S): if |S| < 3 then { 如果S中点数少于3个，就直接返回 } return m = S中所有点的x坐标的中位数 L = S中所有x坐标小于m的点构成的集合 R = S \ L { R包含S中排除L后剩下的元素 } minimum_perimeter(L) { 分别递归求解 L 和 R 中的最小周长三角形 } minimum_perimeter(R) { 求解的结果保存在变量 min 中 } T = {(x,y): |x-m|

ACM题目：众数给定含有n个元素的多重集合S,每个元素在S中出现的次数称为该元素的重数.多重集S中重数最大的元素称为众数二次函数中,求使三角形周长最小的点的坐标怎么求在三角形ABC中,点E在AC上点N在BC上,在AB上找一点F,使三角形ENF的周长最小怎么证明如图所示,由一些点组成形如三角形的图形,每条“边”(包括两个顶点)有n(n为整数,且n＞1)个点,每个图形总的点数s是多如图所示,由一些点组成形如三角形的图形,每条边.每条“边”（包括两个顶点.）n（n＞1）个点,每个图形总的点数s是多少? 在坐标系中,点M(6,0),点N(x,y)在第一象限,x+y=-8,设三角形OMN的面积为S 写出S与X之间函数关系式求如图平行四边形ABCD中,点O是对角线AC上一点,若S平行四边形ABCD=40,求S三角形AOB+S三角形COD的值已知三角形ABC中,点M为AB中点,角ACM+角B=90度,三角形CMB的三边为连续整数.求三角形ABC的面积. 如图,在三角形ABC中,点E在AC上,点N在BC上,在AB上找一点F,使三角形ENF的周长最小,并说明理由. 将n比作点,s比作线段,求n与s的关系? 已知：如图,四边形ABCD的对角线AC与BD相交于点O 求S三角形AOB：S三角形AOD=S三角形COB：S三角形COD DE是三角形ABC的中位线,M是DE的中点,CM的延长线交AB于点N,求S△DMN:S△CEM的值