B. Line Segments

问题描述

在欧几里得平面上给定两个点 $(p_x, p_y)$ 和 $(q_x, q_y)$。

你从起点 $(p_x, p_y)$ 开始，将执行 $n$ 次操作。在第 $i$ 次操作中，你必须选择任意一个点，使得你当前位置与该点之间的欧几里得距离*恰好为 $a_i$，然后移动到该点。

判断在执行完所有操作后，是否可能到达终点 $(q_x, q_y)$。

*点 $(x_1, y_1)$ 和 $(x_2, y_2)$ 之间的欧几里得距离为 $\sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}$。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$ $(1 \leq t \leq 10^4)$。接下来是测试用例的描述。

每个测试用例的第一行包含一个整数 $n$ $(1 \leq n \leq 10^3)$ — 序列 $a$ 的长度。

每个测试用例的第二行包含四个整数 $p_x, p_y, q_x, q_y$ $(1 \leq p_x, p_y, q_x, q_y \leq 10^7)$ — 起点和终点的坐标。

每个测试用例的第三行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ $(1 \leq a_i \leq 10^4)$ — 每次操作要移动的距离。

保证所有测试用例的 $n$ 的总和不超过 $2 \cdot 10^5$。

输出

对于每个测试用例，如果执行完所有操作后可能到达终点 $(q_x, q_y)$，则输出 “Yes”；否则，输出 “No”。

你可以以任何大小写形式输出答案。例如，字符串 “yEs”、“yes”、“Yes” 和 “YES” 都将被识别为肯定回答。

题解

对于每次移动，我们可以选择以当前位置为中心、半径为 $a_i$ 的圆上的任意一点。此时，到目标点 $(q_x, q_y)$ 的距离范围将变为 $[\max(0, d - a_i), d + a_i]$，其中 $d$ 是当前位置到 $(q_x, q_y)$ 的距离。我们将这个范围重写为 $[d_{min}, d_{max}]$。

• 我们从初始范围 $[d_{min}, d_{max}]$ 开始，其中 $d_{min} = d_{max} = d$，而 $d$ 是从 $(p_x, p_y)$ 到 $(q_x, q_y)$ 的距离。
• 对于每次移动 $i$，我们按如下方式更新范围：
  • $d'_{min} = \max(0, \min(|d_{min} - a_i|, |d_{max} - a_i|))$
  • $d'_{max} = d_{max} + a_i$
  • 如果 $a_i \geq d_{max}$ 或 $a_i \geq d_{min}$，那么新的最小距离可以为0，所以 $d'_{min} = 0$。
  • 为下一次迭代更新 $d_{min} = d'_{min}$ 和 $d_{max} = d'_{max}$。
• 所有移动结束后，如果 $0$ 在最终的范围 $[d_{min}, d_{max}]$ 内，那么就有可能到达目标点。

提交链接