OpenKattis
National University of Singapore

Yikes - Bikes!

In recent years the riders in the Tour de France bicycle race have been having problems with dogs running in the road, causing expensive damage to bicycles and serious injuries to riders. In this problem you will take the point of view of a dog named Max. Just as the peloton approaches, Max notices a juicy rabbit in the field on the opposite side of the road. He decides to make a dash across the road. Your task is to determine if Max will safely cross the road if he begins his dash at a given time.

The road is ten meters wide and straight in this part of the country. Max’s dash will be in a straight line at ninety degrees to the road’s center line. He will run at a constant speed of $M \; (0<M<20)$ meters per second. His body can be represented by a circle of diameter one meter projected onto the road surface. See the diagram below.

All the cyclists are in single file racing down the center line of the road, all at the same speed, $B \; (0<B<40)$ meters per second. Each bicycle can be represented by a line segment of length two meters. Its projection onto the road’s surface is collinear with the center line of the road. The bicycles are spaced such that their projections form a dashed line with a distance of two meters between the end of one line segment and the beginning of the next. If, at any time during Max’s dash, his circle touches or is intersected by one or more line segments representing the bicycles, a collision will occur.

Assume that at $t=0$, Max is in position to begin his dash (His circle is completely on the sidewalk, with the edge of the road collinear with one edge of Max’s circle). Assume also that, at $t=0$, the front endpoint of the line segment used to represent the lead bicycle is exactly $D$ meters from the line that Max will take to cross the highway. There are $10$ cyclists in the peloton.

\includegraphics[width=0.8\textwidth ]{RabbitRacea}
Figure 1: Initial Setup for Max’s Dash

Input

Input begins with a positive integer $N$ ($1 \leq N \leq 40$) giving the number of problem sets to follow.

Then, follows four lines for each problem set, each line containing one value as follows:

  • a real number $M$ ($0.01 \le M<20$) giving Max’s speed in meters per second, then

  • a real number $B$ ($0.01 \le B<40$) giving the speed of the cyclists in meters per second, then

  • a real number $D$ ($0\leq D \leq 50$) giving the distance in meters between the front of the lead bicycle at $t=0$ and the line that Max will use to dash across the highway

  • a real number $T$ ($0 \leq T \leq 20$) giving the start time in seconds of Max’s dash

The real values are given with at most $15$ digits after the decimal point.

Output

For each problem set output a single line giving one of the phrases, “Max beats the first bicycle”, “Max crosses safely after bicycle $k$”, ($1 \leq k \leq 10$), or “Collision with bicycle k” ($1 \leq k \leq 10$). If multiple collisions could occur, report only the first.

You may assume that increasing or decreasing the value of $D$ by $10^{-9}$ would not change the answer.

Sample Input 1 Sample Output 1
3
5.0
5.0
5.0
0.0
5.0
5.0
6.3
0.0
5.0
5.0
0.0
5.9
Collision with bicycle 1
Max beats the first bicycle
Max crosses safely after bicycle 9