回 帖 发 新 帖 刷新版面

主题:第69次编程比赛结果

题目贴:http://www.programfan.com/club/post-280816.html
-------------------------------------------------------------
2楼(liyaha):最朴素的算法,效率很低,但是结果正确。n超过2000就慢得要命,呵呵。
4楼(scutdx2005):算法的基本思路是对的,就是按距离排序,然后从最小距离选择,逐步扩大选择的范围。但是结果错误。
5-7楼(apart789):算法没太看懂,呵呵。结果错误。
9楼(ayxg):算法基本同4楼。结果对很多数据都错误。
11-13楼(abc123!!!):算法也是没看太明白,似乎基本思路同2楼。结果错误。
16-17楼(jowenshaw):算法也是先对距离排序再选择。结果错误。
18-19楼(ckeryradish):算法与4楼类似,但是判断三角形是否有效是通过面积来进行的。结果对很多数据都错误。
无楼(tjs125):算法也是先排序,然后选择。tjs125在循环条件的选择上,和在最后退出条件上做了很大改进,所以效率非常高。可惜的是结果对少部分数据错误,比如:p0,p1,p2,p3分别是(30,38),(46,64),(77,23),(17,38)时是有解的,但tjs125程序判断为无解;而且当n>=5000后,耗时就比较长了。估计可能是判断三角形的有效性上存在问题。(晕,刚才才发现你今天早上又修改了程序,只好重测)

综上所述,只有2楼的程序是正确的。因此我宣布本次编程比赛的冠军是liyaha。大家祝贺liyaha并请他主持下次的编程比赛。

(关于测试数据:由于我的题目上说明是随即分布的点,因此所有的点的坐标都是通过随机函数生成的,点A的坐标也是通过随机数生成的)

回复列表 (共28个回复)

21 楼

多谢楼主的指点!
   楼主也很会选数据啊,其实从理论上,你的这组数据因该是可以的通过判断的。
但我的三角型判断方式存在固有的缺点,那就是计算角度的时候的精度问题,不管double以及 π 的精度有多高,因为毕竟不是理论值,实际计算总是存在偏差,导致本该为三角形的却没误判了,我特意测试了你提供的数据,其实按理论上应该是不会误判的,实际却没有。

   还是华罗庚的那句话说的好:数离开形少直观,形离开数难入微;
 
   三角型判断还得按楼主的叉积方式,看来最先是走错方向了,但其实角度在判是否有解时还是有很大的优势(理论情况下),比如有一批特殊点全分布在 直线 y = x + y0 - x0 + 1 的上侧时,楼主的判断方式应该是判不出来的,但重角度判就没问题(理论值)。
   期待下一次的比赛吧!

22 楼

是的,我的判断函数存在问题,我在程序中也说明了。但是ppc提供的矩阵方式判断是不存在我的问题的,而且速度也比我的快,你可以试着实现一下。

至于数据嘛,呵呵,不是我选的,而是随机产生的,测试的组数多了自然就碰上这些数据了。我一般在速度允许的情况下测试10w组左右,呵呵。

23 楼

给评分啊

24 楼


一、游戏种类: 棋牌游戏
    全套源码包括:1.升级 2.斗地主 3.两副牌斗地主 4.疯狂斗地主 5.五十K 6.诈金花 7.梭哈 8. 围棋 9.象棋 10.五子棋 11.四国军棋 12.麻将 13.连连看 14.摇摇乐 共计14款。         

二、源码价格: 请登陆我们网站查询。
  
三、交易方法:     
  
    1)确定购买后,我们首先会发送给您一份测试文件。      

    2)您可以通过网上银行远程支付、支付宝等形式支付。

    3)您将得到的:十四款游戏完整源代码+一份数据库备份文件(SQL数据库)

四、购买联系: 

    QQ: 137666755 
    TEL:0371-61626625
    Email:systerm32@gmail.com
    http://www.gamemaker.net.cn
五、其他:该源码有说明文档,注解详细,另:我们提供一定的技术支持,适合参考或二次开发,我们暂不提供后续开发

25 楼

但是liyaha的答案有一种极限情况貌似没有考虑进去
当a, b ,c, p四个点处于同一线上时,程序也会认为p点在三角形内。

26 楼


[em18]

27 楼

ei...

失败了...

28 楼

结果尽然是这样
。。。

我来回复

您尚未登录,请登录后再回复。点此登录或注册