拯救 $Pika$ -题解

对于题目，我们先看另一种情况。

easy version

假设墙壁为 $x^2+y^2=1$

起始点固定在 $(-1,0)$ 。

行走方式可以选择为

向正上方走，用自由向量表示为 $\vec{n_1}=(0,1)$
向指定方向走，与 $x$ 轴正半轴夹角为 $\theta$ ，保证 $0<\theta<\dfrac{\pi}{2}$ ，用自由向量表示为 $\vec{n_2=(\cos\theta,-\sin\theta)}$ 。

在这种情况下两种行走方式必定是交替进行的，并且行走的次数与 $\theta$ 有直接关系，由圆周角等于圆心角的两倍，可以标出下图对应的角度，因为角度 $\theta$ 并不会发生改变，因此每次行走的角度对应的弧长一定是相等的。假如最开始选择方向是第 $0$ 次，起点与第 $2$ 次选择方向所处位置就是这个弧，以此类推，第 $2,4,6,\cdots,2i$ 之间形成的弧长度一定相等，奇数同理，如果在弧度之下看这个弧的长，那就是 $\pi-2\theta$，每一次的弧一定不会相交。因此，当下一次弧必须与之前弧相交时，就是不能行走的时候，也可以转化为每次加$\pi-2\theta$，当下一次将会超过 $2\pi$ 时，就是需要打破墙壁的时候。

在这个情况下，最终的答案应该是 $\dfrac{2\pi}{\pi-2\theta}$ ，对于算出来的小数，如果是整除，需要额外减去 $1$ ，其他情况下直接舍去小数即可，可以统一为对最终结果向上取整并减 $1$ ，即 $\lceil\dfrac{2\pi}{\pi-2\theta}\rceil-1$。

middle version

现在看目前题目的情况，墙壁为一个椭圆 $\dfrac{x^2}{a^2}+\dfrac{y^2}{b^2}=1$ ，并且角度固定为 $\dfrac{\pi}{4}$ ，因此我们可以将其进行坐标系变化，转化为刚才那种情况，即将 $x$ 变化为 $ax$ ， $y$ 变化为 $by$ 即可得到方程 $x^2+y^2=1$ ，此时原本的固定的角度$\dfrac{\pi}{4}$ 会发生改变，$\theta$ 为 $\arctan\dfrac{a}{b}$ ，为了减少精度损失，因为 $\arctan x+\arctan\dfrac{1}{x}=\dfrac{π}{2}$，因此 $\dfrac{\pi}{2}-\theta=\arctan \dfrac{b}{a}$ 。

根据 easy version 的结论， $\lceil\dfrac{2\pi}{\pi- 2\theta}\rceil-1=\lceil\dfrac{2\pi}{2\arctan \dfrac{b}{a}}\rceil-1=\lceil\dfrac{\pi}{\arctan\dfrac{b}{a}}\rceil-1$ ，编程可以使用 acos(-1) 尽可能求出 $\pi$ 的近似值，因此最终要求的就是 $\lceil\dfrac{\arccos(-1)}{\arctan\dfrac{b}{a}}\rceil-1$ ，注意开 long long 。

hard version

其实本来出的 middle version 角度并不是固定的，假设角度不是固定的话，$\theta^`$ 为 $\arctan({\dfrac{a}{b}\tan\theta})$ ，其他道理与后面大致相同了。

另一种解法

可以通过光线反射的角度来看待这一题，可参考CHOJ上另一题光与镜。

示例代码

#include <iostream>
#include <cmath>
#include <iomanip>
using namespace std;
int main()
{
    long long a, b;
    cin >> a >> b;
    double theta = atan(1.0 * b / a);
    cout << setprecision(11) << ceil(acos(-1) / theta) - 1 << endl; // 向上取整-1
}

拯救 Pika -题解