主题:关于第69次编程比赛
boxertony
[专家分:23030] 发布于 2008-07-17 11:31:00
请在此贴提问。
题目贴:http://www.programfan.com/club/post-280816.html
回复列表 (共26个回复)
11 楼
tjs125 [专家分:0] 发布于 2008-07-25 00:48:00
楼主!
不好意思,来晚了,虽然不能参加比赛,但能您能不能提供一组数据或者一个程序检测我们的程序是否正确啊,让我也没有白做啊!麻烦楼主了!
另外,你的题目中有说n的范围为3到1000000,可你在函数的定义头里面的定义是int n,这样n的最大值不就只有32767了嘛!
12 楼
boxertony [专家分:23030] 发布于 2008-07-25 08:56:00
这段时间忙,没来得及弄呢。等我测试完了,再把数据给你吧,呵呵。
至于int类型的范围问题,现在一般来说都是使用32位编译环境,int为32位,所以不存在你说的问题。比赛不考虑使用象turbo c之类的16位编译环境。
13 楼
tjs125 [专家分:0] 发布于 2008-07-26 18:06:00
楼主,还想问一句,为什么我在Dev-C++4.9.9.2中定义x与y数组时,一当数组个数大于6到7万的时候,程序就会出错,所以1000000就没法测试了,是不是内存不够啊?
我有测试,只要是随机分布的数组,我的函数是非常快的!
楼主能不能帮我验证一下我的函数是否正确啊!非常期待!
我先谢谢了!
14 楼
boxertony [专家分:23030] 发布于 2008-07-26 18:43:00
局部变量是在栈中分配内存的,而栈的大小是受限制的,系统不同栈的大小可能也不同,一般为64K,所以你的数组稍大就出错。把他作为全局或者静态局部,或者动态分配即可。
对了tjs125,你的程序中的M_PI值是什么?
15 楼
ckeryradish [专家分:140] 发布于 2008-07-26 20:17:00
To:tjs125
给三组测试用例 x0 =0; y0 =0;
int pointsX[] = {-1, 0, 1};
int pointsY[] = {-2, 0, 2};
int pointsX[] = {1, 2, 3, 4};
int pointsY[] = {1, 2, 3, 5};
int pointsX[] = {-1, -3, 0, 1};
int pointsY[] = {-2, -2, 0, 2};
最后还需产生很多的随机数来测
To:boxertony
google M_PI
另外我的代码中abs(dfDistance_AB + dfDistance_AC - dfDistance_BC) <= DOUBLE_EPSILON [em10]冠军是没我的份了,但测试的时候可以帮我改成fabs么?
16 楼
tjs125 [专家分:0] 发布于 2008-07-26 20:48:00
TO boxertony:
M_PI是指圆周率,3.1415926
楼主的局部变量与全局变量的内存分配知识让我长了见识,谢谢了!
17 楼
ati9200pro [专家分:100] 发布于 2008-07-27 18:40:00
最近在工作太忙居然没有来得及参加...
今天才看到题目...汗...
我考虑,是不是可以以给顶点为中心,向外检索矩形或圆周范围的点,那么就可以把需要检索的点控制在最小范围...不过空间解析几何忘得差不多了...没空看书.郁闷。
18 楼
tjs125 [专家分:0] 发布于 2008-07-27 19:18:00
我说说我的思路,恳请楼主和大家指正与意见!
第一步、
先把所有的(x,y)点转化为以A(x0,y0)为中心的极坐标形式。
就是(ρ,θ);
ρ:代表点(x,y)到A(x0,y0)的距离。程序中为 dis
θ:代表点(x,y)与A(x0,y0)的逆时针角,范围为[0,2π),程序中为 deg
第二步、
然后将这些点按距离 ρ 的值从小到大进行希尔排序,形成数组 pv[n];
第三步、
按照 pv[n] 的排序结果,从小到大开始搜索目标点。
具体做法如下:
1、
首先按 ρ = 0 排除与 A(x0,y0) 重合的点,求得开始下标 beginI ;
2、
从最小的 3 个点出发求满足条件的 MinDis。
3、
然后扩展到 4 个点内求满足条件的 MinDis。
4、
依次扩大求解点的范围,当求解完第 k 个点以内的 MinDis 后,判断所求的
MinDis是否为所有点的最小值,这一步很关键,否则也是不停的找,也相当于遍历
了所有点,那就不可取了。
判断依据:
当 [color=0000FF]MinDis < (pv[k + 1].dis + pv[beginI + 1].dis + pv[beginI].dis)[/color]时
就可断定 MinDis 的最小值了,此时即可结束循环,求出解。
5、
其实内部我还有在细化,再判断了一次,加了一些限制循环的条件,原理是一样
的,差不多。
第四步、
我的三角形的判定条件为:
假如有 3 个点与(x0,y0)的角分别为 A, B, C 范围在[0,2π)内。
我是任取 2 点,假如取了A与B,先求出 2 点与(x0,y0)的组成的夹角的对[color=FF0000]顶角
的[/color]范围,minR1至maxR1,minR2至maxR2,可能会有 2 个范围,因为对顶角可能垮过
x 的正半轴,因我所定义的角为 [0,2π)。
假如 C 在所求的 minR1至maxR1,minR2至maxR2 范围内,则C就满足要求。
按我以上的算法,要是随机分布的点,计算是相当的快的,与多小没有太大关系,应为一般他的求解 K 是很少的,但有个特殊情况是在无解的时候,是要遍历所有点的。这样就慢了,其实也可以对(ρ,θ)的 θ 进行排序,得出 θmin 与 θmax,
然后判断 θmax - θmin < π ,是则无解,就不要遍历了,但我的程序没有做这个工作。
以上我的愚见,恳请大家的指正与跟好的意见。
19 楼
boxertony [专家分:23030] 发布于 2008-07-27 20:36:00
to tjs125:
(1)为什么不使用快速排序?当n很大时,排序算法制约了程序的速度
(2)为什么排除与 A(x0,y0) 重合的点?我的题目没有要求排除啊
(3)没仔细看你判断三角形的函数,我怀疑你的函数实现可能还存在问题,导致有些数据出错
20 楼
tjs125 [专家分:0] 发布于 2008-07-27 20:55:00
我现在正在查,包括三角形判断等,好像三点时是有不对。
另外关于速度,我想我的程序肯定没什么问题,我这边的测试程序速度是很快啊!开到1000000也就2秒多一点。
另外采用希尔排序是因为它短,不要递归,可以放到函数中间,省事!但他算法复杂度和快速算法一样,都是 nloa2n 啊,具体我也没比较过,相信差别不会很大!
到时候还请楼主多指点!
我来回复