回 帖 发 新 帖 刷新版面

主题:第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个回复)

11 楼


  呵呵,大家回答的都不错啊

12 楼

count 与 ++count1 是什么啊?怎么通不过编译啊?

13 楼

抱歉,我当时为了测试循环次数用的,忘了删除了。

14 楼

楼主:
   我检查了我的程序,主要是三角形的判断上对点在边上以及顶点上考虑不够周到,我已做了修正,能方便帮我测试一下吗?

15 楼

很遗憾的告诉楼主 当我欣然编译您的程序的时候 出现了以下5个错误:

--------------------Configuration: minidistanceR - Win32 Debug--------------------
Compiling...
minidistanceR.cpp
D:\vc程序\minidistanceR.cpp(10) : error C2065: 'sqrt' : undeclared identifier
D:\vc程序\minidistanceR.cpp(74) : error C2065: 'assert' : undeclared identifier
D:\vc程序\minidistanceR.cpp(77) : error C2065: 'DBL_MAX' : undeclared identifier
D:\vc程序\minidistanceR.cpp(78) : error C2065: 'INT_MAX' : undeclared identifier
D:\vc程序\minidistanceR.cpp(97) : error C2065: 'qsort' : undeclared identifier
Error executing cl.exe.

minidistanceR.exe - 5 error(s), 0 warning(s)

16 楼

麻烦楼上自己补充头文件的包含工作

17 楼

抱歉,刚发现我的PtInTriangle函数还存在一点小问题,已经修改。

18 楼

[quote]楼主:
   我检查了我的程序,主要是三角形的判断上对点在边上以及顶点上考虑不够周到,我已做了修正,能方便帮我测试一下吗?[/quote]
我重新测试了一下,你的程序还存在如下的问题:
(1)ReRangeAB函数不需要返回值,你却设置返回值类型为int,但是你在最后又不用return返回值。编译应该会有警告信息吧?

(2)PointV pv[ARRAYLEN];最好动态申请,你结果改成全局数组,而且大小设置为3,害得我测试时老出错(我以为你没改这儿,呵呵)

(3)关于三角形的检测可能没有问题了,但是最后的三重循环倒是被你改出问题来了,呵呵,退出条件改得有问题,n=2000就要好几分钟才能出结果

19 楼

不好意思,真是辛苦楼主了,太感谢楼主这么耐心的帮我测试!
也谢谢楼主的指点,ReRangeAB我已改为 void 了, PointV pv 我也动态申请了。
但我在测试的时候,时间一直是没问题啊?还麻烦楼主再帮我看看,为什么你那边总是说 n 一大,时间就很长啊?
我有点困惑!

20 楼

我找到你的问题所在了。你在求距离的时候用的下面的表达式:
sqrt((x[i] - x0) * (x[i] - x0) + (y[i] - y0) * (y[i] - y0))
我没有给出x,y坐标的范围,所以实际上这些坐标相乘是可能溢出的,而你的程序假定坐标都小于1000,因此在我这儿出错,而在你那儿是正常的。

另外,你的判断三角形的函数还有问题,比如下面的数据:
    x        y
74    50 
82    38
66    87
---------------------
80    41 // x0, y0

我来回复

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