B. 线段 详细题解

题目重述

在平面上给定起点 $S(p_x, p_y)$ 和终点 $T(q_x, q_y)$。需要执行 $n$ 次操作，第 $i$ 次操作必须从当前位置移动到距离恰好为 $a_i$ 的任意点（方向任意）。判断是否存在一种移动方案，使得 $n$ 次操作后恰好到达终点 $T$。

问题转化

设第 $i$ 次移动的向量为 $\vec{v_i}$，满足 $|\vec{v_i}| = a_i$，最终的总位移为：

$$\vec{R} = \sum_{i=1}^n \vec{v_i}$$

我们需要判断是否存在一组方向选择，使得 $\vec{R} = \overrightarrow{ST} = (q_x - p_x, q_y - p_y)$。

核心观察

一维情形的启发

在一维数轴上，每次移动距离固定为 $a_i$，方向可选正或负。最终位置为：

$$\sum_{i=1}^n \pm a_i$$

• 最大可能距离：$S = \sum_{i=1}^n a_i$
• 最小可能距离：设 $M = \max(a_1, a_2, \dots, a_n)$
  • 若 $M \le S - M$，则最小距离为 $0$
  • 否则最小距离为 $M - (S - M) = 2M - S$

且可达位置与 $S$ 具有相同的奇偶性。

二维情形的扩展

在二维平面上，由于方向可以在 $360^\circ$ 范围内任意选择，自由度更高。第 $i$ 步的向量可以表示为：

$$\vec{v_i} = a_i(\cos\theta_i, \sin\theta_i)$$

其中 $\theta_i$ 为任意角度。

两个向量的情况

对于两个固定长度的向量 $\vec{v_1}$ 和 $\vec{v_2}$，它们的合向量 $\vec{R} = \vec{v_1} + \vec{v_2}$ 的长度范围为：

$$|a_1 - a_2| \le |\vec{R}| \le a_1 + a_2$$

并且这个区间是连续的（通过改变两向量夹角可以连续变化）。

多个向量的情况

将前 $k-1$ 个向量的合向量视为一个新的向量，其模长可以在某个区间 $[L_{k-1}, S_{k-1}]$ 内连续变化。再与第 $k$ 个向量合成，根据三角不等式：

$$|L_{k-1} - a_k| \le |\vec{R}_k| \le S_{k-1} + a_k$$

由于 $L_{k-1}$ 和 $S_{k-1}$ 之间是连续的，合成后的模长也可以连续变化。不断迭代，最终可达的模长集合是一个连续区间。

关键结论

设：

• $S = \sum_{i=1}^n a_i$
• $M = \max(a_1, a_2, \dots, a_n)$

则经过 $n$ 步后，从起点出发能到达的所有点构成的集合是：

• 圆心在起点，半径为 $S$ 的圆盘（如果 $M \le S - M$）
• 半径为 $[2M-S, S]$ 的圆环（如果 $M > S - M$）

即最小可达距离为：

$$d_{\min} = \max(0,\ 2M - S)$$

最大可达距离为：

$$d_{\max} = S$$

并且区间 $[d_{\min}, d_{\max}]$ 内的所有距离都是可达的。

为什么没有奇偶性限制？

在一维中，每次改变方向只能改变 $2a_i$，导致奇偶性限制。但在二维中，可以通过连续旋转向量来连续改变合向量的模长，因此区间是连续的，没有离散限制。

算法步骤

1. 计算起点到终点的欧几里得距离：

   $$D = \sqrt{(p_x - q_x)^2 + (p_y - q_y)^2}$$

2. 计算步长总和：

   $$S = \sum_{i=1}^n a_i$$

3. 计算最大步长：

   $$M = \max_{i=1}^n a_i$$

4. 计算最小可达距离：

   $$d_{\min} = \begin{cases} 0, & \text{if } M \le S - M \\ 2M - S, & \text{if } M > S - M \end{cases}$$

5. 判断是否可达：

   $$d_{\min} - \varepsilon \le D \le S + \varepsilon$$

   其中 $\varepsilon$ 是一个很小的正数（如 $10^{-9}$），用于处理浮点精度误差。

正确性证明

充分性

若 $D$ 在区间 $[d_{\min}, S]$ 内，我们可以通过构造法证明可达：

1. 当 $M \le S - M$ 时，可以通过调整使前 $n-1$ 步的合向量与第 $n$ 步反向，从而得到任意小于 $S$ 的模长。
2. 当 $M > S - M$ 时，最大步长无法被完全抵消，最小模长就是 $2M - S$，且通过调整夹角可以得到该区间内的任意值。

必要性

由三角不等式：

• 总位移长度不超过各步长度之和：$|\vec{R}| \le \sum a_i = S$
• 总位移长度不小于 $\max(0, 2M - S)$（这是由三角形不等式多次应用得到的下界）

因此，若 $D$ 不在 $[d_{\min}, S]$ 内，则一定不可达。

复杂度分析

• 时间复杂度：$O(n)$ 每个测试用例
• 空间复杂度：$O(1)$ 额外空间
• 总 $n$ 不超过 $2 \times 10^5$，完全可行

示例验证

示例1

$n=2,\ a=[3,3],\ S=[1,1],\ T=[5,1]$

• $S = 3+3 = 6$
• $M = 3$
• $M \le S-M = 3$，故 $d_{\min}=0$
• $D = \sqrt{(1-5)^2 + (1-1)^2} = 4$
• $0 \le 4 \le 6$ ✅ 输出 Yes

示例3

$n=2,\ a=[4,5],\ S=[100,100],\ T=[100,100]$

• $S = 4+5 = 9$
• $M = 5$
• $M > S-M = 4$，故 $d_{\min} = 2 \times 5 - 9 = 1$
• $D = 0$
• $0 < 1$ ❌ 输出 No

注意事项

1. 整数运算优先：计算 $D$ 时使用 sqrt，但比较时注意精度
2. 数据类型：使用 long long 存储坐标差平方和，避免溢出
3. 浮点精度：使用 $\varepsilon = 10^{-9}$ 容忍计算误差
4. 特殊情况：当 $S=0$ 时（$n=0$，但题目保证 $n\ge 1$，$a_i\ge 1$，所以 $S\ge 1$）