JaWs
Time limit1sMemory limit128 MB
Given two rows of equilateral triangles, drop the upper row onto the lower one and report where it settles or which side it slides off.
- Level
Hard8 of 10
- Topics
- Geometry, Simulation, Implementation
- Solved
- No attempts yet
Problem
"Sigh! Where are those good old bloody days?" pondered Bob, the old shark — once the fearsome slayer of the deep blue waters — as his tears joined the endless water of the ocean. After years of butchering, Bob's teeth have lost their regular shape, and the poor old shark now has trouble closing his jaws. He wants to program his PDA to help him find the shape his teeth take when his jaws are closed, and we want to help him write that program!
Call the sequence of Bob's lower teeth LT and the sequence of his upper teeth UT. For simplicity, treat LT as a row of adjacent equilateral triangles (all sides equal), with the bases of every triangle lying on one horizontal line. UT has the same structure, except that its triangles are upside down (see Figure 1).

Figure 1. A snapshot of Bob's teeth.
Assume the left endpoint of the base of the leftmost tooth in LT is at , so the bases of all LT triangles lie on the x-axis. Call the left endpoint of the base of the leftmost tooth in UT the reference point. Initially the reference point is placed so that:
- no tooth tip in LT and no tooth tip in UT share the same x-coordinate,
- UT lies above LT (the y-coordinate of the reference point is greater than zero),
- LT and UT do not overlap anywhere.
Starting from such a placement, UT falls straight down; its bases stay horizontal during the fall (UT never rotates). UT keeps falling until it touches some point of LT. From that moment UT slides downward along LT (to the left or to the right) until it can slide no further. Throughout the motion LT stays fixed and UT never rotates. Depending on its starting position, UT may slide off to the left or to the right and drop below LT (imagine the old shark in that state!); it is also possible for the tips of some upper teeth to end up below the line (the Dracula style!). Your program must decide whether UT falls off to the left or to the right; otherwise it must report the final position of the reference point after UT stops moving.
Input
The first line contains a single integer (), the number of test cases. The data for each test case follows.
The first line of a test case contains an integer (), the number of triangles in LT. Each of the next lines contains one integer (), the side length of an LT triangle, listed from left to right.
The next line contains three numbers , , and . The first two are the initial coordinates of the reference point and may be arbitrary real numbers; is the number of triangles in UT (). Each of the following lines contains one integer (), the side length of a UT triangle, listed from left to right.
To avoid floating-point trouble, you may assume that during the motion of UT the distance between the tips of any two triangles (one from LT and one from UT) is never less than .
Output
Print one line per test case. If UT comes to rest on LT, print two real numbers — the and coordinates of the reference point after UT stops — each rounded to exactly three digits after the decimal point. If instead UT slides off to the left of LT, print WM; if it slides off to the right of LT, print MW. The output is case-sensitive.