问题描述

Sleeping Cup's Jump 是一种特殊的舞蹈动作，舞者需要使用尽量少的移动次数在二维舞台上从点 $(x_1, y_1)$ 移动到 $(x_2, y_2)$。每次移动可以选择一个实数 $d$ 和一个角度 $\phi \in (-\frac{\pi}{2}, \frac{\pi}{2})$，并从起始位置 $(x, y)$ 移动到目标位置 $(x + d \times \phi, y + d \times \tan \phi)$。

数学性质分析

移动方式的数学表达

每次移动的位移向量为：

• $d \times x = d \times \phi$
• $d \times y = d \times \tan \phi$

关键性质推导

将两式相除得：$\frac{d \times y}{d \times x} = \frac{\tan \phi}{\phi}$

由于 $\phi \in (-\frac{\pi}{2}, \frac{\pi}{2})$ 且 $\phi \neq 0$，有以下性质：

1. 符号相同：$\tan \phi$ 和 $\phi$ 同号，因此 $d \times x$ 和 $d \times y$ 必须同号
2. 比值大于1：在 $\phi \in (-\frac{\pi}{2}, \frac{\pi}{2})$ 范围内，$\frac{\tan \phi}{\phi} > 1$，因此 $\lvert d \times y \rvert > \lvert d \times x \rvert$

最小移动次数判断

0 次移动

当起点和终点相同时，不需要移动： $d \times x = 0$ 且 $d \times y = 0$

1 次移动

当位移满足以下条件时，可以通过一次移动到达：

1. $d \times x \neq 0$
2. $d \times y \neq 0$
3. $\lvert d \times y \rvert > \lvert d \times x \rvert$
4. $d \times x$ 和 $d \times y$ 同号

2 次移动

其他所有情况都需要两次移动，包括：

1. dx 或 dy 为 0
2. $\lvert d \times y \rvert \le \lvert d \times x \rvert$
3. $d \times x$ 和 $d \times y$ 异号

AC code：

#include <bits/stdc++.h>
using namespace std;

int main() {
    freopen("tangent.in", "r", stdin);
    freopen("tangent.out", "w", stdout);
    long long x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    long long dx = x2 - x1;
    long long dy = y2 - y1;
    if (dx == 0 && dy == 0) {
        cout << 0 << endl;
    } else if (dx != 0 && dy != 0 && (dx > 0 && dy > 0 || dx < 0 && dy < 0) && abs(dy) > abs(dx)) {
        cout << 1 << endl;
    } else {
        cout << 2 << endl;
    }
    return 0;
}

显然 $d,\varphi \ne 0$。考虑一次移动中轨迹的斜率 $k=\dfrac{\tan \varphi}{\varphi}$。画图可知，当 $\varphi \in (-\dfrac{\pi}{2},0) \cup (0,\dfrac{\pi}{2})$ 时，$k \in (1,+\infty)$：

也就是说，如果直线 $AB$ 的斜率 $k_{AB}>1$ 且存在，那么就可以从 $A$ 一次性移动到 $B$。

很明显，如果我们第一次移动时选择 $d=10^{100},\varphi=\dfrac{\pi}{4}$，那么一次移动后的位置 $X$ 与终点 $Y$ 之间的斜率将会极其接近 $\dfrac{4}{\pi}$，显然可以从 $X$ 一次性移动到 $Y$。整个过程一共移动了 $2$ 次，所以答案总是不超过 $2$。

综上，本题的结论是（设 $P$ 为起点，$Q$ 为终点）：

• $P$ 与 $Q$ 重合时答案为 $0$；
• $k_{PQ}>1$ 且存在时答案为 $1$；
• 以上两个条件都不满足时答案为 $2$。

#include <bits/stdc++.h>
using namespace std;
#define y1 Y1
int steps(int x1, int y1, int x2, int y2)
{
	if (x1 == x2 && y1 == y2) return 0;
	if (x2 > x1 && y2 - y1 > x2 - x1) return 1;
	if (x1 > x2 && y1 - y2 > x1 - x2) return 1;
	return 2;
}
int main()
{
	freopen("tangent.in", "r", stdin);
	freopen("tangent.out", "w", stdout);
	int x1, y1, x2, y2;
	cin >> x1 >> y1 >> x2 >> y2;
	cout << steps(x1, y1, x2, y2) << endl;
	return 0;
}