TOAD 21 - Searching for the truth
似乎我 YY 出一个不同的方法？
Problem
无穷平面上有两个点 ，两点距离为 。 一步可以移动到距离不超过 1 的地方。而且 移动后可以知道距离 是远了还是近了。求一种方法使得 移动 步后两点距离不超过 1 。 表示 $$ \lim_{x \to \infty} \frac{f(x)}{g(x)} = 0.
<!-- more --> # Solution 假设我们找到一条过 $A$ 的直线，使得 $B$ 到这条直线的距离不超过 $\frac{1}{2}$ ，那么这个问题就很容易了，我们沿着这条直线走即可，最后几步微调一下。 给定一条直线，如何判断 $B$ 到这条直线的距离不超过 $\frac{1}{2}$ 呢？我们沿与直线垂直的方向跳，左右各跳一次，如果两次都是距离变远了，那么距离就不超过，否则一定超过 $\frac{1}{2}$ 。 所以现在的任务是找到一条直线。我们建立一个直角坐标系，先检验两条坐标轴是否满足要求，如果不满足，那么我们可以找到 $B$ 在哪个象限。 考虑如图所示区域（不会 tikz 只好用 GeoGebra 了），假设我们已经把 $B$ 点的范围确定在 $\alpha$ 内，这次我们判断角 $\alpha$ 的平分线 $AD$ 是否可行。如果 $AD$ 不行，我们就可以将角度减小为原来的一半。  时间复杂度？我觉得是 $O(\log D)$ 的。注意 $\frac{AD}{AE} = \frac{1}{2 \cos \frac{1}{4}\alpha} = \frac{\sin \frac{1}{4}\alpha}{\sin \frac{1}{2} \alpha}$ 。当 $\alpha \to 0$ 时， $\frac{AD}{AE} = \frac{1}{2}$ 也就是 $AE = 2AD$ ，所以只需要 $O(\log D)$ 次即可找到要求直线，而 $O(\log n) = o(D)$ 。 # nonsense 本来这篇文章在去北京旅游之前就写完了的，但是由于 jekyll 突然之间挂了我就不好说啥了。 回学校 pacman -Syu 后发现 libpng 挂了，幸亏 QQ 还可以上然后借助文学巨匠 @wzy 的力量终于修好了。然后再试试 jekyll 发现居然好了真是太令人开心了。 所以说一个生活用的 Linux 就是一个配置好了后不 Syu 的 Arch Linux 么 233 不过我用 Linux 的一个很重要的原因就是 学zhuang习bi 吧。wzy 说把 Windows 玩坏了他不知道该怎么办，其实我把 Linux 玩坏了不也是玩不会来了 233 由于到北京的第一天笔记本就来了（这神奇的速度），于是这几天天天在玩 Windows 8 水人人水 GM 水贴吧水各种各样的网站。一开始的时候还是有点不习惯，现在感觉差不多还行吧。不过一堆设置没有真是蛋疼。（为啥我感觉现在我用的输入法都这么准呢？一定是我的错觉） 所以说一直拖着拖到现在才发这篇文章真是对不起了（又没人看说啥对不起呢 —— 不要在意这些细节） 今天下了个 SSD 的订单，明天应该就可以来，我还不会装呢，到时候请老师帮忙吧。光驱是 SATA2 真是对不起啊，不过 SSD 要是能达到 SATA2 的上界我也不得不服。