Balloons

Consider the problem of navigating a hot air balloon. Our first guess might be that there is nothing we can do — flights seem to be at the mercy of the wind: you go up, you drift with the wind, you come down. However, there is one fact about the weather we can often exploit: the wind does not blow in the same direction at all altitudes.

In the scenario illustrated below, at low altitudes (< 1000 ft) the low wind blows a little west of north, while at higher altitudes (> 1000 ft) the high wind blows a little north of east. To travel from a starting point $S$ to a target point $X$, we could launch to a high altitude, ride the high wind until we are about halfway along the north/south dimension, then drop down and use the low wind to reach the destination. With good timing, and assuming the wind does not change direction, we can land accurately at the destination.

Write a program to compute balloon flight plans. For simplicity, assume there are exactly two wind directions, both stable. The goal is to find the fastest possible path, or to determine that no path is possible.

Assume we can raise and lower the balloon without moving significantly over the ground, as if the change in elevation were instantaneous. However, an artificial time penalty of 30 seconds is added for every elevation change (either up or down), to discourage changing altitude too often.

There is one complication: air traffic control restricts us to a flight corridor of width $W$ centred on the straight line between the starting and target points. We may not fly outside this corridor, so we may have to follow some kind of zigzag path.

The first line contains an integer $N$, the number of problems to solve. Each of the following $N$ lines describes one problem with 9 floating-point values:

• $S_x, S_y$ — the coordinates of the starting position, in metres;
• $X_x, X_y$ — the coordinates of the target position, in metres;
• $L_x, L_y$ — the low wind velocity vector, in metres per second;
• $H_x, H_y$ — the high wind velocity vector, in metres per second;
• $W$ — the width of the flight corridor, in metres.

You may assume that neither the low wind nor the high wind ever blows exactly in the direction from $S$ to $X$.

For each problem, print one line. Print either the word Impossible, or the time required for the flight (including time penalties) in seconds, rounded to the nearest second.