[悬赏]奇妙的三角形

此方丽莎 · 发表于 2010-1-8 14:49:51

求解命题：在地图上随机生成12个点，将这12个点每3个分为一组，分别连接在一组中的3个点，使得连线构成三角形，并且任意两个三角形不相交。
要求：①.使用war3的脚本语言，任意一次计算不要超过执行时间上限
            ②.尽量不要有对象的泄露，在计算过程中使用到的辅助点对象需要排泄
            ③.在地图中使用闪电效果演示你生成的4个符合要求的三角形

如：

这是生成的12个点
图示1.jpg

这是符合要求的连法

这是错误的连法

本命题的悬赏金额为2WGAB，由本人账户支付
作为开源项目，最后得出的正确算法任何人都可取得使用权
但作者保留所有权，任意使用该算法的作品中，请注明算法作者
大家可以积极讨论学习，正确答案以上传的演示为准！

此方丽莎 · 发表于 2010-1-8 14:55:12

你可以去中国银行将GAB兑换成日元，然后将日元兑换成RMB，再用RMB去买Q币

反正GAB比日元的汇率高~~

eff · 发表于 2010-1-8 15:03:53

这个题目可以用A*做

此方丽莎 · 发表于 2010-1-8 15:07:16

EFF有没有兴趣？

<font color · 发表于 2010-1-8 15:10:01

此题有一极其简单的解法。

此方丽莎 · 发表于 2010-1-8 15:11:24

[s:177]

那当然是越简单越好

eff · 发表于 2010-1-8 15:11:53

-，-递归也是可以做出来的

疯人￠衰人 · 发表于 2010-1-8 15:13:29

比当年做外接多边型的复杂

alexries · 发表于 2010-1-8 15:13:43

阿，斜率……？

<font color · 发表于 2010-1-8 15:15:24

此题本身并不严密。因为生成的12个点可能无解。比如9个以上的点一直线。

疯人￠衰人 · 发表于 2010-1-8 15:16:51

正常递归会超过执行上限的
12个点可能组成的三角形数为220*98*20*1=431200

此方丽莎 · 发表于 2010-1-8 15:17:00

那么，需要算法自己识别这种状况吖

alexries · 发表于 2010-1-8 15:17:41

阿，的确这样就悲剧了呢。

疯人￠衰人 · 发表于 2010-1-8 15:18:54

引用第10楼<font color=gre于2010-01-08 15:15发表的 :
此题本身并不严密。因为生成的12个点可能无解。比如9个以上的点一直线。

3个在同一直线上的点
也可以看做是一个特殊的三角形即可

此方丽莎 · 发表于 2010-1-8 15:20:17

只是这样的话，演示中是很难看清几个三角形是否相交了

eff · 发表于 2010-1-8 15:20:52

按照A*的思想，是这样的

首先选择一个最外围的点（假设所有的X,Y都是正数，到圆点点的距离最远或者最近那个点）

其次依次链接离这个点最近并且没有被链接过/标记的点，如果形成了带交叉的路径就暂时标记下来，然后调整标记附近的连接直到最后形成一条无交叉的路径，然后把点按照三个一组连起来即可。

疯人￠衰人 · 发表于 2010-1-8 15:28:39

引用第16楼eff于2010-01-08 15:20发表的 :
按照A*的思想，是这样的

首先选择一个最外围的点（假设所有的X,Y都是正数，到圆点点的距离最远或者最近那个点）

其次依次链接离这个点最近并且没有被链接过/标记的点，如果形成了带交叉的路径就暂时标记下来，然后调整标记附近的连接直到最后形成一条无交叉的路径，然后把点按照三个一组连起来即可。

这个方法不是一次成功的吧……
那么需要返回？
那么还是会超过执行上限

eff · 发表于 2010-1-8 15:28:45

不过如果我没记错的话，按照最近原则连出来的东西应该就是无交叉的

eff · 发表于 2010-1-8 15:29:36

或者说出现了交叉就回溯，这个就是A*的基本思想

反正就是先算，然后不行就回溯，深度始终是元素的最大数量，记录空间消耗是2

疯人￠衰人 · 发表于 2010-1-8 15:30:32

改了……

		自动登录	找回密码
密码			点一下