#P3755. The Training of Chain Lightning
The Training of Chain Lightning
Description
Chain Lightning is an advanced Lightning Magic and it is not very easy to master it. After casting this spell to a target, the chain lightning will find the nearest target which is not affected by previous chains and pass on through. So it is difficult to calculate when we need to hit a moving target by chains. Sram has failed in the test of Chain Lightning and it will cause great trouble if he failed again next week. His brother Mars decided to help him do some training. Since Sram can hit the first target precisely, now he should try to improve his calculating skill.
Now Sram stands on (0,0) and there are N pillars in the room (which can be used as conductors). Sram is not allowed to move and the pillars will not move either. Mars starts from (A,0) and then run along the positive X-axis. The cast range and chain range of chain lightning are both 50. Sram tried to hit the first target pillar at second 0 and Mars started running at the same time. Each chain will cost 1s (which means at second 1, the chain lightning will start from the first target pillar, find and hit the nearest target including other unchained pillars and Mars, and the next hit happened at second 2 and so on). Since hit by chain lighting is extremely painful and the power of chain lighting will be lower as the hit number increases, Mars decide to choose a speed so that he will receive the least damage no matter how clever Sram is. For the convenience of novice Sram, Mars will not change his speed after he started. Suppose that Sram can always hit Mars as soon as possible, and Mars have a maximum speed of V per second (But he can not reach this speed, poor Mars~)
Note that Mars’s speed is a real number and is in the range of (0,V), so that he cannot select to stay still even if that is the best way.
It is guaranteed that from a certain pillar, at most one pillar will be chosen as the next chain pillar. If Mars and other pillar have the same distance from the certain active pillar, Mars will definitely be hit-_-. Pillars on the positive X-axis will not block Mars’s way.
Input
There are multiple test cases.
The first line of each case is an integer N (N ≤ 30), representing the number of pillars. Next line contains two integers A and V, representing the starting point of Mars is (A,0) and the maximum speed is V per second. (10 ≤ A ≤ 100, 10 ≤ V ≤ 45) Next N lines contain 2 real numbers each, representing the X-Y position of the ith pillar. The input data in finished with a case of N=0.
Output
Output contains only an integer, representing the earliest time Mars will definitely be hit. If Mars can choose a speed so that chain lightning will never hit him, output -1 instead.
3
100 10
50 0
100 0
-50 0
3
100 40
50 0
100 0
-50 0
0
2
-1
Source
POJ Monthly Contest - 2010.04.04, Mars