← 返回题目列表

Codeforces · 2119/B

B. 线段

中文机器翻译题面 查看原题
PIKASONIC - Lost My Mind (feat.nakotanmaru)

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

您从起点 $$$(p_x,p_y)$$$ 开始,并将执行 $$$n$$$ 操作。在第 $$$i$$$ 操作中,您 必须 选择任意点,使得当前位置与该点之间的欧氏距离$$$^{\text{∗}}$$$ 为 正是 $$$a_i$$$,然后移动到该点。

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

$$$^{\text{*}}$$$$$$(x_1, y_1)$$$ 和 $$$(x_2, y_2)$$$ 之间的欧氏距离为 $$$\sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}$$$

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 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 \le a_i \le 10^4$$$) — 每个操作中要移动的距离。

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

输出

对于每个测试用例,输出“是"如果所有操作后都能到达终点$$$(q_x,q_y)$$$;否则输出"No".

您可以在任何情况下输出答案(大写或小写)。例如,字符串“是", "是", "是“,和”是”将被视为积极响应。

示例

输入
复制

5
2
1 1 5 1
3 3
3
1 1 3 3
2 3 4
2
100 100 100 100
4 5
1
5 1 1 4
5
2
10000000 10000000 10000000 10000000
10000 10000

输出
复制

Yes
Yes
No
Yes
Yes

注意

这是一张显示第一个测试用例可能移动的图片。点$$$r_1$$$的坐标是$$$(3,1+\sqrt{5})$$$。

第一个测试用例。

这是一张显示第二个测试用例可能移动的图片。点$$$r_1$$$的坐标为$$$(1+\sqrt{3},0)$$$,点$$$r_2$$$的坐标为$$$\left(-\frac{(\sqrt{3}+4)(3\sqrt{3(149-24\sqrt{3})}-7\sqrt{3}-38)}{104},-\frac{\sqrt{3(1331-764\sqrt{3})}+12\sqrt{3}-27}{104}\right)$$$。

第二个测试用例。

对于第三个测试用例,可以证明没有一组动作可以满足所有要求。

这是一张显示第四个测试用例可能移动的图片。

第四个测试用例。