主题：第三十次编程比赛第一题的结果
yunzhou008 [专家分：410] 发布于 2006-06-11 18:16:00
下面我公布第三十次编程比赛的结果：
maobingwen 5楼：不能通过编译。
shijizhisheng 10楼 不能通过编译。
天边蓝 12楼 OK。
sllone 7楼 OK。
通过编译的两个程序，都是用了两重循环，
而天边蓝的程序不需要 每次SQRT显然要好
一点。
因此 我宣布 本次比赛结果（第一题）冠军
为天边蓝！
希望你组织下一次比赛的第一题。
回复列表 （共19个回复）
沙发
iAkiak [专家分：8460] 发布于 2006-06-11 20:07:00
请原谅我不能直接贴出答案。
这题其实关键是使用求凸包算法。
求凸包算法复杂度为O(n*logn)，得到在凸包上的顶点d个。再进行d^2的求最大距离。
d在随机数据情况下约为4*n^0.5，在n为30000时，d约为700。
整个程序的复杂度为O(nlogn + d^2) = O(nlogn + 16n)，约为624313。
板凳
yunzhou008 [专家分：410] 发布于 2006-06-11 20:29:00
没关系的，不贴出来也好。
因为像你上面说的那样，贴出来了估计我也看不懂。
你一直是我在论坛的偶像。
不过我发誓我要追上你的。
3 楼
iAkiak [专家分：8460] 发布于 2006-06-11 20:41:00
汗...我很菜的。
我不能贴是因为自己写会写错：）
4 楼
ckeryradish [专家分：140] 发布于 2006-06-11 21:02:00
to iAkiak
我自己想了一下,我只是想到要用两重循环,
不过由于帖子没有隐藏,我见到的和我想到的几乎一模一样,
另外最近也比较忙,因此我就没写出来.可是老大你既然想到凸包算法怎么不写啊.
凸包算法我连听都没听过呢,不然的话我可又长见识了.不写出来,那就讲讲伪代码之类的可以么?
5 楼
sarrow [专家分：35660] 发布于 2006-06-11 21:07:00
凸包算法
应该就是求“凸多边形”--不过，我没有想到O(n*logn)复杂度的算法...
6 楼
yunzhou008 [专家分：410] 发布于 2006-06-11 21:40:00
严重同意ckeryradish 4楼的说法
7 楼
iAkiak [专家分：8460] 发布于 2006-06-11 22:05:00
求凸包算法。
什么是凸包：直观的说，平面上n个点，用橡皮筋围起来，橡皮筋接触到的点构成凸包。
选最低的点O(n)，计算它到所有其他点的矢量的方向O(n)，按逆时针方向对其他点排序O(n*logn)。
使用栈，记录凸包上的点。
最低的点一定在凸包上。压栈
排序得到的第一个点也一定在凸包上。压栈
现在保证栈内至少2个点。
对其余的点依次遍历。
如果栈顶点A到下一个点B的矢量方向相对栈顶2点矢量方向是逆时针的，那么新顶点B可以加入栈。（它可能是凸包上的点）反之，则栈顶点A必然不是凸包上的点，弹出A
继续判断栈顶点直到B压栈或者栈内只剩余2个顶点为止（此时B点也压栈成为新栈顶）。
最后一个点加入后还需要尝试加入最低点以排除末尾的多余内点。
判断完所有顶点后，栈内点依次为凸包的逆时针顶点。这个过程为O(n)(注意，虽然有加入顶点和排除顶点，但一个顶点最多被加入和排除各1次)
总复杂度最高的地方就是排序O(n*logn)
8 楼
sarrow [专家分：35660] 发布于 2006-06-11 22:31:00
形象，方便理解！
凯凯兄厉害！
9 楼
yunzhou008 [专家分：410] 发布于 2006-06-11 23:10:00
[em3]
看不太懂
[em8]
10 楼
fenix124 [专家分：70] 发布于 2006-06-12 12:47:00
即使用了凸包算法,但是在最坏的情况下,可以专门出数据,还是O(n^2).
我来回复
您所在位置：