63 - ZOJ Monthly, February 2008 - 1003
After supper, Farmer John's cows like to take a walk in the farm. They stride in the sunset, wondering about the miracle of life. Moreover, to award the cows for their great milking effort, Farmer John has brought for every one of them a Bluetooth communication device, and now the cows can send short messages to each other! Excited to send messages around, though, they have found a problem. The communication ranges of theses Bluetooth devices are very short, which means two cows staying too far away can not send messages to each other directly. Being a retired high-tech software company employee, Farmer John tries to work around this problem by implementing a routing software, which routes a message from the sender to the receiver via a series of intermediate cows.
More precisely, the farm is modeled as a rectangle, and cows as single points. At time 0 cow i is at position (Xi,Yi). She randomly picks a point on the farm, and walks there with a randomly chosen constant speed. She always takes the shortest path between the two points, i.e. her path is a line connecting the two points. She would greet some other cows and send some short messages on her way. Once she reaches that point, she picks another point on the farm and walks to the new destination, possibly with a different speed. She repeats this process until the walking session is over. So her walk is actually a piecewise linear path.
For a message sent from cow a to cow b, Farm John's software will schedule a path C1->C2->...->Cm where C1 = a and Cm = b. The message will be sent first from cow C1 to C2, then from C2 to C3, etc. until it reaches cow Cm. Since the Bluetooth devices have a maximum communication range of D, the message can only be sent from Ck to Ck+1 when their Euclidean distance is equal to or less than D, for 1<=k<=m-1, otherwise this message waits in the buffer of Ck's communication device until it can be sent. The waiting time for this message is defined to be the time when the message reaches Cm minus the time when it is initiated by C1. We assume the transmitting time of any message is always zero, and the buffer of any cow's device is sufficiently large.
For example, consider the scenario of only two cows. At time 0 cow 1 is at (0,0) and moves toward (10,0) with constant speed 1, and cow 2 moves from (10,0) to (0,0) with the same speed. D = 2 and at time 0 cow 1 sends a message to cow 2. The message can not be sent immediately since the two cows are too far away, so it waits in cow 1's buffer until time 4 when their distance decreases to 2. The message is then instantly sent and received, and the waiting time for this message is 4 - 0 = 4.
Farmer John needs to implement the routing software so that knowing in advance each cow's walking(i.e. their choices of new destinations and speeds during the walking session), for each message sent from cow a to cow b at time t, the waiting time for this message is minimized. You need to write a program to solve this problem: Given a description of all cows' walking, your program must output the minimum waiting time for each message to be sent.
The input consists of multiple test cases.
On the first line of each case are three integers N(2<=N<=100), T(1<=T<=1000) and D(0<=D<=100), the number of cows on the farm, the length of the walking session and the communication range of the Bluetooth devices. We denote the starting time of the walking session as time 0.
Next N lines describe each cow's walking. The ith line of these starts with three integers Xi, Yi and Ki(1<=Ki<=50). (Xi,Yi) denotes the initial position of cow i within the farm at time 0. Ki blocks follow on the same line and these blocks describe cow i's piecewise linear walking path in order. Each block consists of three integers Xi,j, Yi,j and Vi,j, meaning cow i walks from (Xi,j-1,Yi,j-1) to (Xi,j,Yi,j) with speed Vi,j in her jth linear path for 1<=j<=Ki with Xi,0=Xi and Yi,0=Yi. You can assume(Xi,j,Yi,j) always locates within the farm and is a different position from (Xi,j-1,Yi,j-1), Vi,j is between 1 and 20 inclusive, and all X's and Y's are between 0 and 100 inclusive. The walking session is long enough to allow each cow to reach her last destination, and once a cow reaches her last destination, she stays there until the end of the session. Cows may occupy the same position at the same time.
On the next line is an integer M(1<=M<=20), the number of routing queries. Next M lines each have three integers a, b and t, meaning that cow a sends a short message to cow b at time t. You can assume 1<=a,b<=N, 0<=t<=T and that a and b are always different.
Process to the end of file.
For each query, output on a line the minimum waiting time for the corresponding message. The answer must be rounded to two decimal places. If the message can not be sent to the receiver before the walking session is over, output -1 instead.
2 10 2
Author: LIU, Xin