Background

最近点对问题:给定 $n$ 个二维欧几里得平面上的点 $p_1, p_2, \dots, p_n$,请输出距离最近的两个点的距离。

一个广为人知的随机做法是这样的:

我们充分发扬人类智慧:
将所有点全部绕原点旋转同一个角度,然后按 $x$ 坐标排序
根据数学直觉,在随机旋转后,答案中的两个点在数组中肯定不会离得太远
所以我们只取每个点向后的 $5$ 个点来计算答案
这样速度快得飞起,在 $n=1000000$ 时都可以在 1 s 内卡过

——P1429 平面最近点对(加强版)最高赞题解。

当然,上面这个声称看起来就不对——因为随一次失败概率显然可能很大。之前也有传言这个有类似根号的正确性下界保证,然后我暑假整理模板的时候也相信了这一点,不过,仔细想起来,这是不对的!

当然,不对得并不是很明显,我先和 Chihao 讨论得出了一个构造方法,然后在几何画板上画出来后,发现角度存在非常牛逼的等角关系,交给几何大师证明了一下发现显然对;之后,路过的毛哥哥一语中的,发现构造的点就在一个圆上,然后就发现这个题性质更美妙了。

因此我就出了这个题,放在了 IEEE 21 算法课第一次上机作业的附加题里:

Continue reading

不围棋(NoGo)是一种在 \(9 \times 9\) 的棋盘上进行的一种棋类游戏,游戏下子限制为禁止在棋盘上产生围棋中的吃子,最终无法行动的一方失败,另一方获得胜利。详见 Botzone 上的 NoGo。 = = 这个东西作为 AI 大作业就意味着要……爆肝……然后我把我的 Documentation 粘在下面了…… 还是挺高兴的,第一次写出了 UCT,打爆了上次想写却没写出好的五子棋 AI 的我。

Continue reading