National University of Singapore

Within Arm's Reach


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?


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.


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.



$\leq $


$\leq $


Number of segments in the robotic arm


$\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


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
5 3
4.114 -2.842
6.297 -0.784
5.000 3.000
Sample Input 2 Sample Output 2
-8 -3
-3.745 -1.404
-5.618 -2.107