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 2d-plane. 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 vx and the vertical speed can't exceed vy.
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)?
There are multiple test cases. There are two parts for each case. The first part is one line with four integers N, vx, vy and t (2 <= N <= 9, 0 < vx, vy <= 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 xi and yi (-1000000 <= xi, yi <= 1000000), represent the coordinate for the ith magpie. There will not be two different magpies in the same point initially.
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 1E-6 will be accepted.
2 1 1 1 0 0 0 7
For the sample, in time 0, Yue Lao pushes the first magpie to right with vx = 1. In time 1 Yue Lao pushes the second magpie to left with vx = -1. The two magpies will meet an time 4.
Author: HANG, Hang
Source: ZOJ Monthly, February 2009