
ZOJ Problem Set  3159
It is the Valentine's day! Yue Lao decides to have a meeting for the magpies to construct the pie bridge(magpie bridge). There are N magpies in the sky. In order to hold a meeting, Yue Lao should make all the magpies at the same place in the same time. A magpie can be consider as a dot in the 2dplane. Initially, all the magpies stay still in some place. The only instruction Yue Lao can do is to push a magpie. Yue Lao can push a magpie in any direction. After Yue Lao pushs a magpie, the magpie starts moving in that direction with a constant speed. Yue Lao's power is limited, so there is a limit for the speed of the magpie: the horizontal speed can't exceed v_{x} and the vertical speed can't exceed v_{y}. Yue Lao can push a magpie at most once. Besides, Yue Lao can't push magpies too often. After a push, he needs to rest at least t seconds for the next push. When two magpies meet at the same point, they will not collide with each other and will stay moving or stay still. Now the question is, what is the minumum time it needs to take for Yue Lao to achieve his goal (make all the magpies moves to the same place at the same time)? Input There are multiple test cases. There are two parts for each case. The first part is one line with four integers N, v_{x}, v_{y} and t (2 <= N <= 9, 0 < v_{x}, v_{y} <= 100, 0 <= t <= 100), represent the number of magpies, the horizontal speed limit, the vertical speed limit, and the time interval Yue Lao needs to rest between two pushes. The second part consists with N lines. Each line consists of two integers x_{i} and y_{i} (1000000 <= x_{i}, y_{i} <= 1000000), represent the coordinate for the i_{th} magpie. There will not be two different magpies in the same point initially. Output The output of each test case should be a single line, the minimum time for Yue Lao to achieve his goal. All result that have relative or absolute error less than 1E6 will be accepted. Sample Input 2 1 1 1 0 0 0 7 Sample Output 4.000000000000000 Hint For the sample, in time 0, Yue Lao pushes the first magpie to right with v_{x} = 1. In time 1 Yue Lao pushes the second magpie to left with v_{x} = 1. The two magpies will meet an time 4. Author: HANG, Hang Source: ZOJ Monthly, February 2009 