TOAD 21 - Searching for the truth

似乎我 YY 出一个不同的方法？

Problem

无穷平面上有两个点 \(A, B\) ，两点距离为 \(D\) 。\(A\) 一步可以移动到距离不超过 1 的地方。而且 \(A\) 移动后可以知道距离 \(B\) 是远了还是近了。求一种方法使得 \(A\) 移动 \(D + o(D)\) 步后两点距离不超过 1 。\(f(x) = o(g(x))\) 表示 \[\lim_{x \to \infty} \frac{f(x)}{g(x)} = 0\] 。

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 的上界我也不得不服。