OpenKattis
National University of Singapore

Within Arm's Reach

/problems/withinarmsreach/file/statement/en/img-0001.png

João wants to join the robotic football team of his university. However, since he knows little about robotics and mathematics, he decided to build a $2$-dimensional robotic arm to bootstrap his knowledge.

The robotic arm is composed of $N$ segments of various lengths. The segments can form any angle between them, including configurations that make it appear to self-intersect when viewed from above. The robotic arm works great, but it is not trivial to position the arm’s tip as close as possible to given $x$, $y$ target coordinates with so many joints to control. Can you help João?

Task

Given the robotic arm description and target coordinates relative to the arm’s origin, calculate a configuration that places the arm’s tip as close as possible to the target.

Input

The first line contains $N$, the number of segments composing the robotic arm. $N$ lines follow, each with an integer $L_ i$ describing the length of the $i$th segment from the fixed point until the arm’s tip. There is one more line with $2$ integers: the $x$, $y$ coordinates of the target point to reach.

Constraints

$1$

$\leq $

$N$

$\leq $

$20$

Number of segments in the robotic arm

$1$

$\leq $

$L_ i$

$\leq $

$1\, 000$

Length of the $i$th segment

$-20\, 000$

$\leq $

$x, y$

$\leq $

$20\, 000$

Target coordinates to attempt to reach

Output

The output should contain $N$ lines, each containing two real numbers $x_ i$, $y_ i$ indicating the coordinates of the tip of the $i$th segment.

The length of the $i$th segment computed from the solution and input $L_ i$ may not differ by more than $0.01$. Similarly, the absolute error between the solution’s distance to the target and the minimum possible distance to the target cannot exceed $0.01$.

Note that, in general, there are many solutions. Your program may output any of them.

Explanation for Sample Input 1

Sample output 1 corresponds to the drawing on the left:

\includegraphics[width=0.95\textwidth ]{sample-output1a.png}

\includegraphics[width=0.95\textwidth ]{sample-output1b.png}

The drawing on the right corresponds to the following, equally acceptable output for sample input 1:

3.923 3.100
1.118 2.037
5.000 3.000

Explanation for Sample Input 2

\includegraphics[width=0.5\textwidth ]{sample-output2.png}

Sample Input 1 Sample Output 1
3
5
3
4
5 3
4.114 -2.842
6.297 -0.784
5.000 3.000
Sample Input 2 Sample Output 2
2
4
2
-8 -3
-3.745 -1.404
-5.618 -2.107