ZOJ Problem Set - 1785
"Sigh! Where are those good old bloody days?" Pondered Bob, the old shark, the former slayer of the deep blue waters, with his tears joining the infinite water of the ocean. Butchering for years, Bob's teeth has lost their regular shape, and the poor old shark is now in trouble closing his jaws. He wants to program his PDA to help him find the shape of his teeth when his jaws are closed and we want to help him write this program!
We name the sequence of Bob's lower teeth as LT and the sequence of his upper teeth as UT. For the sake of simplicity, consider LT as a sequence of adjacent equilateral triangles (i.e., with equal sides). All bases of the triangles lie on the same horizontal straight line. UT has a similar structure, except that the triangles are upside-down (Figure 1).
Assume the left endpoint of the base of the leftmost tooth in LT has the coordinates (0, 0), so the bases of all triangles in LT lie on the x axis. We name the left end point of the base of the leftmost tooth in UT, the reference point. Initially, the coordinates of the reference point is given such that:
Given a placement of UT and LT conforming to the above conditions, UT starts falling downward such that the base of the triangles remain horizontal during its fall, i.e. UT does not rotate. UT continues to fall, until it touches some point in LT. At this time, UT slides downward (to the left or right) over LT until it cannot slide any further. During this motion, LT is fixed and UT never rotates. Note that UT may have an initial position such that it slides downward either from left or right, and falls below LT (Imagine the old shark in that state!). Also it is possible that the tips of some upper teeth finally pass the line y = 0 (the Dracula-style!). Your program should determine whether UT falls down from left or right, or otherwise, finds the final position of the reference point after it stops moving.
In order to avoid floating-point arithmetic errors, you may assume that the input has the property that during the motion of UT, the distance between tips of any two triangles in LT and UT is never less than 0.1.
Source: Asia 2002, Tehran (Iran)