Bouldering#3546
Bouldering is a style of rock climbing. Boulderers climb up the rock with bare hands without supporting ropes. Your friend thought that it would be interesting and exciting, so he decided to try a bouldering gymnasium. Since your friend had not tried bouldering before, he chose the beginner's course. However, in the beginner's course, he found that some pairs of rocks were too far from each other, making it very difficult to reach all rocks safely. He gradually becomes anxious and wonders whether the course is actually suitable for beginners. So, he asked you to write a program that simulates the way he climbs and checks whether he can reach the goal rock successfully.
For the sake of convenience, we assume that a boulderer consists of line segments, representing his body, his right arm, his left arm, his right leg, and his left leg.
One end of his body is connected to his arms at their endpoints. The other end of the body is connected to his legs at their endpoints. The maximum length of his body, arms, and legs are , , and , respectively. He climbs up the wall by changing the length of his body parts from to their maximum length, and by twisting them at any angle ( degrees). Refer to the following figure representing possible body arrangements.
Figure 1: An example of possible body arrangements.
line segments representing his body, arms, and legs. The lengths of his body, arms, and legs are , , and , respectively. The picture describes his head as a filled circle for better understanding, which has no meaning in this problem.
A boulderer climbs the wall by grabbing at least three different rocks on the wall with his hands and feet. In the initial state, he holds rocks with his hands and feet. Then, he changes one of the holding rocks by moving his arms or legs. This is counted as one movement. His goal is to grab a rock called the "destination rock" with one of his body parts. The rocks are considered as points with negligible size. You are to write a program that calculates the minimum number of movements required to grab the destination rock.
The input data looks like the following lines:
x_1\ y_1
x_2\ y_2
x_n\ y_n
The first line contains (5 \leq n \leq 30), which represents the number of rocks.
The second line contains three integers , , (1 \leq A, B, C \leq 50), which represent the length of the body, arms, and legs of the climber respectively.
The last lines describe the location of the rocks. The -th contains two integers x_i and y_i (0 \leq x_i, y_i \leq 100), representing the and coordinates of the -th rock.
In the initial state, the boulderer is grabbing the st rock with his right hand, nd with his left hand, rd with his right foot, and th with his left foot.
You may assume that the first rocks are close enough that he can grab them as described above.
The last rock is the destination rock.
Your program should output the minimum number of movements to reach the destination rock.
If it is impossible to grab the destination rock, output -1.
You may assume that, if , , would be changed within , the answer would not change.
The following figures show just an example of how the boulderer climbs up to the destination in the minimum number of movements. Note that the minimum number of movements can be achieved by taking different climbing paths, shortening body parts, rotating parts, etc.
Figure 2: An example of minimum movement for sample input .
Figure 3: An example of minimum movement for sample input .
Example 1