Cowmunication

Time Limit: 5 Seconds
Memory Limit: 32768 KB

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 (X_{i},Y_{i}). 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 C_{1}->C_{2}->...->C_{m} where C_{1} = *a* and C_{m} = *b*. The message will be sent first from cow C_{1} to C_{2}, then from C_{2} to C_{3}, etc. until it reaches cow C_{m}. Since the Bluetooth devices have a maximum communication range of *D*, the message can only be sent from C_{k} to C_{k+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 C_{k}'s communication device until it can be sent. The **waiting time** for this message is defined to be the time when the message reaches C_{m} minus the time when it is initiated by C_{1}. 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.

**Input**

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 i^{th} line of these starts with three integers X_{i}, Y_{i} and K_{i}(1<=K_{i}<=50). (X_{i},Y_{i}) denotes the initial position of cow *i* within the farm at time 0. K_{i} 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 X_{i,j}, Y_{i,j} and V_{i,j}, meaning cow *i* walks from (X_{i,j-1},Y_{i,j-1}) to (X_{i,j},Y_{i,j}) with speed V_{i,j} in her j^{th} linear path for 1<=*j*<=K_{i} with X_{i,0}=X_{i} and Y_{i,0}=Y_{i}. You can assume(X_{i,j},Y_{i,j}) always locates within the farm and is a different position from (X_{i,j-1},Y_{i,j-1}), V_{i,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.

**Output**

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.

**Sample Input**

2 10 2

0 0 1 10 0 1

10 0 1 0 0 1

1

1 2 0

2 10 0

0 0 1 10 0 1

10 0 1 0 0 1

1

1 2 0

6 100 10

32 32 1 12 52 16

8 30 1 94 44 8

65 19 3 91 1 7 89 34 12 58 20 10

38 65 3 7 20 16 51 18 3 71 97 8

26 5 2 70 65 14 75 29 5

93 87 3 64 75 14 89 100 1 40 37 3

5

3 5 0

4 3 0

3 6 0

4 2 0

1 4 0

**Sample Output**

4.00

5.00

-1

17.16

-1

1.73

1.13

**Author: ***LIU, Xin*

Submit
Status