Robot Arms 2

题目描述

给定长度为 $N$ 的序列 $A = (A_1, A_2, \dots, A_N)$，元素为正整数，以及整数 $x$ 和 $y$.
判断是否可以在 $xy$ 平面上放置 $N+1$ 个点 $p_1, p_2, \dots, p_N, p_{N+1}$，使其满足下列所有条件。（允许将两个或多个点放在相同坐标处。）

$p_1 = (0, 0)$。 $p_2 = (A_1, 0)$。 $p_{N+1} = (x, y)$。 点 $p_i$ 与 $p_{i+1}$ 之间的距离为 $A_i$.（$1 \leq i \leq N$） 线段 $p_i p_{i+1}$ 与 $p_{i+1} p_{i+2}$ 构成 $90$ 度角。 （$1 \leq i \leq N - 1$）

输入格式

输入从标准输入按以下格式给出： $N$ $x$ $y$ $A_1$ $A_2$ $\dots$ $A_N$

输出格式

如果可以放置 $p_1, p_2, \dots, p_N, p_{N+1}$ 以满足问题陈述中的所有条件，则输出 $Yes$；否则输出 $No$。

3 -1 1
2 1 3

Yes

5 2 0
2 2 2 2 2

Yes

4 5 5
1 2 3 4

No

3 2 7
2 7 4

No

10 8 -7
6 10 4 1 5 9 8 6 5 1

Yes

提示

$2 \leq N \leq 10^3$ $1 \leq A_i \leq 10$ $|x|, |y| \leq 10^4$ 输入中的所有数值均为整数。下图展示了一个放置方案，其中 $p_1 = (0, 0)$、$p_2 = (2, 0)$、$p_3 = (2, 1)$、$p_4 = (-1, 1)$。问题陈述中的所有条件均被满足。
将 $p_1 = (0, 0)$、$p_2 = (2, 0)$、$p_3 = (2, 2)$、$p_4 = (0, 2)$、$p_5 = (0, 0)$ 和 $p_6 = (2, 0)$ 即可满足所有条件。注意多个点可以放在相同坐标处。

标签: AtCoder|abc274D

来源

AtCoder|abc274D