/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
長さ N の正整数列 A = (A_1, A_2, \dots, A_N) および整数 x, y が与えられます。
次の条件をすべて満たすように、xy 座標平面上に N+1 個の点 p_1, p_2, \dots, p_N, p_{N+1} を配置することができるか判定してください。(同じ座標に 2 個以上の点を配置してもよいです。)
- 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
xy 座標平面に 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
Score : 400 points
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