首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 软件管理 > 软件架构设计 >

请问一道计算几何难题

2012-02-16 
请教一道计算几何难题在一个圆内有n个点,这n个点都不在圆上,现在要在圆上求一点,使总共n+1个点所围成的凸

请教一道计算几何难题
在一个圆内有n个点,这n个点都不在圆上,现在要在圆上求一点,使总共n+1个点所围成的凸包面积最大。
请教一下大家算法~

[解决办法]
求n个点的凸包.
得到凸包上的所有顶点 <=n.

任意2顶点做垂直平分线,得到2个与圆的交点,分别以这2个交点为第n+1个点求凸包面积.

遍历得到最大面积.

热点排行