1786. Mineshaft

A plumber has been hired to build an air pipe through a mineshaft from the bottom to the surface. The mineshaft was built without modern technology, so it winds its way up through the earth. Because it is very time consuming to bring the tools necessary to bend the pipe below the surface. the plumber wants to minimize the number of bends in the pipeline.

For example, for the mineshaft in the first picture below, the minimal number of bends in a pipeline from the bottom to the surface is two. Different optimal solutions exist, one of which is shown in the second picture. The bullets indicate the bends in the pipeline.

The two walls of the mineshaft are formed by sequences of straight segments. The numbers of segments in the two sequences may be different. Further, the horizontal distance between the walls of the mineshaft may vary, but is always positive. Both walls start at the same level and end at the same level.

On the way form the bottom of the mineshaft to the surface, the level (the y-coordinate) increases with every segment of a wall. Hence, the mineshaft does not have horizontal plateaus or ‘ceilings’, and at no point does it go back down again.

For the purpose of this task. you may assume the diameter of the pipeline to be 0. At no point may the pipeline cross the walls. In order to attach the pipeline firmly to the wall, each segment of the pipeline has to touch the walls at (at least) two different places. Howeverm, the bending points of the pipeline are weak. They cannot be used to attach the pipeline to the wallls. The end point s of the pipeline, tough, at the bottom and the top of the mineshaft, may be used to attach a segment to the walls.

Hence, the solution in the third picture above(also having two bends) is not allowed, because the lowest segment of the pipeline can be attached to the wall at only one place: at the bottom of the right wall.

The pipeline must start anywhere at the bottom of the mineshaft, and must end anywhere on the imaginary line between the top of the left wall and the top of the right wall. Note, however, that the endpoints of the pipeline may only be used to attach the pipeline, if they touch a wall. In particular, the endpoint at the bottom cannot be attached to any position at the bottom which is not the bottom of a wall.

Finally, the angle that the pipeline makes at a bending point can take value a satisfying -180。< a < 180。 and (of course) a != 0.

Note that sometimes it may be useful to have the pipeline intersect with itself. For example, in the mineshaft below, this is needed to get from the bottom to the top of the mineshaft with only three bends.