102743: [AtCoder]ABC274 D - Robot Arms 2

Problem Statement

You are given a sequence $A = (A_1, A_2, \dots, A_N)$ of length $N$ consisting of positive integers, and integers $x$ and $y$.
Determine whether it is possible to place $N+1$ points $p_1, p_2, \dots, p_N, p_{N+1}$ in the $xy$-coordinate plane to satisfy all of the following conditions. (It is allowed to place two or more points at the same coordinates.)

• $p_1 = (0, 0)$.
• $p_2 = (A_1, 0)$.
• $p_{N+1} = (x, y)$.
• The distance between the points $p_i$ and $p_{i+1}$ is $A_i$. ($1 \leq i \leq N$)
• The segments $p_i p_{i+1}$ and $p_{i+1} p_{i+2}$ form a $90$ degree angle. ($1 \leq i \leq N - 1$)

Constraints

• $2 \leq N \leq 10^3$
• $1 \leq A_i \leq 10$
• $|x|, |y| \leq 10^4$
• All values in the input are integers.

Input

The input is given from Standard Input in the following format:

$N$ $x$ $y$
$A_1$ $A_2$ $\dots$ $A_N$

Output

If it is possible to place $p_1, p_2, \dots, p_N, p_{N+1}$ to satisfy all of the conditions in the Problem Statement, print Yes; otherwise, print No.

Sample Input 1

3 -1 1
2 1 3

Sample Output 1

Yes

The figure below shows a placement where $p_1 = (0, 0)$, $p_2 = (2, 0)$, $p_3 = (2, 1)$, and $p_4 = (-1, 1)$. All conditions in the Problem Statement are satisfied.

Sample Input 2

5 2 0
2 2 2 2 2

Sample Output 2

Yes

Letting $p_1 = (0, 0)$, $p_2 = (2, 0)$, $p_3 = (2, 2)$, $p_4 = (0, 2)$, $p_5 = (0, 0)$, and $p_6 = (2, 0)$ satisfies all the conditions. Note that multiple points may be placed at the same coordinates.

Sample Input 3

4 5 5
1 2 3 4

Sample Output 3

No

Sample Input 4

3 2 7
2 7 4

Sample Output 4

No

Sample Input 5

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

Sample Output 5

Yes

问题描述

给你一个由正整数组成的序列$A = (A_1, A_2, \dots, A_N)$，长度为$N$，以及两个整数$x$和$y$。

• $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$)

约束条件

• $2 \leq N \leq 10^3$
• $1 \leq A_i \leq 10$
• $|x|, |y| \leq 10^4$
• 输入中的所有值都是整数。

输入

输入从标准输入按照以下格式给出：

$N$ $x$ $y$
$A_1$ $A_2$ $\dots$ $A_N$

输出

如果可以在满足问题描述中的所有条件的情况下放置$p_1, p_2, \dots, p_N, p_{N+1}$，则打印Yes；否则，打印No。

样例输入1

3 -1 1
2 1 3

样例输出1

Yes

下图所示是一个放置方式，其中$p_1 = (0, 0)$，$p_2 = (2, 0)$，$p_3 = (2, 1)$，$p_4 = (-1, 1)$。问题描述中的所有条件都得到了满足。

样例输入2

5 2 0
2 2 2 2 2

样例输出2

Yes

将$p_1 = (0, 0)$，$p_2 = (2, 0)$，$p_3 = (2, 2)$，$p_4 = (0, 2)$，$p_5 = (0, 0)$，$p_6 = (2, 0)$放在同一位置满足所有条件。注意，可以将多个点放在同一坐标上。

样例输入3

4 5 5
1 2 3 4

样例输出3

No

样例输入4

3 2 7
2 7 4

样例输出4

No

样例输入5

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

样例输出5

Yes