江苏龙网

  1. 首页 > 生活 > >

在n*m的区域上画凸多边形，最多能有几条边?

这道题是动态规划的题目呀。
先算 1*1 的区域，再算 1*2，1*3 ... 1*m ... 2*m ，3*m ... n*m 的。

■网友
还是等待更好的解答。。

不过对于凸多边形，每条边的辐角是单调变化的。
对于整数隔点，所有的辐角一共有200*200种左右的情况。
所以可以记录以特定角度访问一个隔点的时候之前的边数
然后用动态规划做就差不多了。。
但是边界比较难考虑，可能要枚举横过来那条边的位置。。

好像这个规模直接搜也勉强可以。。。

■网友
在n*m的区域上画凸多边形，最多能有几条边?

加一个自己画的4*4的图，凸包并不一定中心对称。
分成4段也不太好使，右下角一个方块能画两条边

■网友
这样的凸包按照和边界的接点可以分成四段折线，记每段包含边数为f(x, y)：
【在n*m的区域上画凸多边形，最多能有几条边?】 在n*m的区域上画凸多边形，最多能有几条边?

由于凸包一定是中心对称的，所以答案就是2(f(x, y) + f(n-x, m-y))。所以枚举x和y就好了。
至于f(x, y)的计算，是可以动态规划的。


■网友
我来猜测一个正MxM网格下的凸多边形的最大边数K：
在n*m的区域上画凸多边形，最多能有几条边?

修正一下
K=2
其中方括号为取整
估计在MxN网格下，M≠N的时候，需要分一些情况进行讨论，貌似很复杂，我再想想

等待达人给出具体解答吧


    推荐阅读


    上一篇：怎样评价中国的政府网站「我为政府网站找错」这一栏目

    下一篇：怎样理解「select/poll是上下文无关的；epoll是有状态的」