Not an official ACM page
[ Problem G | 1999 ACM Finals problem set | My ACM problem archive | my home page]
The 23rd Annual
ACM International Collegiate
Programming Contest
WORLD FINALS
sponsored by IBM


Problem F
Robot


A robot arm used in an automated factory consists of N connected links: link1 which is connected to link2, ..., and linkN-1 which is connected to linkN. Each link is a straight rod of a specified length, len1, len2, ..., lenN. Between each pair of connected links is a servo, servo2 (between link1 and link2), ..., and servoN (between linkN-1 and linkN) that can be activated to adjust the angle between the connected links. Link1 is also connected by a servo, servo1, to the factory floor (at the point x=0, y=0, z=0 in a Cartesian coordinate system). At the free (unconnected) end of the last link (linkN) is a "hand" that can be used to grasp objects.

In the initial setting of the robot arm, each servo is set to no rotation (0 degrees), and the links in the robot arm coincide with the z-axis. The xy plane is horizontal (the factory floor), and the entire robot arm is initially pointing up, vertically. From this initial setting, each servo can effect a rotation of up to 90 degrees in either of two directions. Servo1 moves the entire robot arm in the xz plane by rotation about the y-axis. Servo2 moves the arm (except link1) in the (perhaps rotated) yz plane by rotation about the x-axis. In a similar manner, each odd-numbered servo can rotate the remaining part of the arm in the (perhaps rotated) xz plane, and each even-numbered servo can rotate the remaining part of the arm in the (perhaps rotated) yz plane. In effect, the servos rotate the links about the y and x-axes of coordinate systems fixed to the end of each link. Counterclockwise rotations about a coordinate axis are produced with positive rotation angles, if we are looking along the positive half of the axis toward the coordinate origin. The sample data has been carefully chosen to illustrate the effects of these rotations.

There are two restrictions on the final positioning of the robot's arm. No part of the arm can be below the factory floor, and the links in the robot's arm cannot intersect with each other (except where they are connected by the servos).

You should check only the final position of the arm.

Given the number of links in a robot's arm, their lengths, and the proposed settings of the servos, first determine if the proposed positioning of the arm is allowable. If the arm can be positioned as proposed, then determine the coordinates of the robot's hand, accurate to three fractional digits. Otherwise identify the first (smallest numbered) servo that has an inappropriate setting, and why that setting is inappropriate. Links are assumed to intersect if they come within 0.001 length units of each other.

Input

The input data will contain multiple test cases. Each test case includes, in order, the number of links, N, their lengths, len1, ..., lenN, and the proposed angles to which the servos (starting with servo1) are to be set. The lengths and servo angles are real numbers, and the number of links is an integer. There will be no more than 10 links in any robot arm. The last test case is followed by a negative integer.

Output

For each test case, display the test case number (starting with 1). Then, if the proposed setting is allowable, display the position of the robot's hand in the original (factory floor) coordinate system (with three fractional digits). Otherwise display the identity of the first servo with an inappropriate setting and why that setting is inappropriate. An output format similar to that shown below is acceptable.

Sample Input

2 25 15 0 90.0
1 1.0 45.0
2 1 1 0 45
4 1 2 3 4 90 0 0 0
3 1 1 1 0 90 90
2 1 1 45.0 45
4 1 1 1 2 0 90 0 90
8 10 1 1 1 1 1 1 2
   0 0 90 0 90 0 90 0
-1

Output for the Sample Input

Case 1: robot's hand is at (0.000,-15.000,25.000)
Case 2: robot's hand is at (0.707,0.000,0.707)
Case 3: robot's hand is at (0.000,-0.707,1.707)
Case 4: robot's hand is at (10.000,0.000,0.000)
Case 5: robot's hand is at (1.000,-1.000,1.000)
Case 6: robot's hand is at (1.207,-0.707,1.207)
Case 7: servo 4 attempts to move arm below floor
Case 8: servo 8 causes link collision
This page maintained by Ed Karrels.
Last updated December 7, 1999