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 that we can often exploit. The wind does not blow in the same direction at all altitudes. In the diagram below we illustrate a possible scenario. At low altitudes (< 1000 ft) the wind (low wind) is blowing a little West of North. At a higher altitude (> 1000 ft) (high wind) it is blowing a little North of East. If our objective is to get from a starting point (S) to a target point (X) we could launch to a high altitude, fly in the direction of the high wind until we are about half way in the North/South dimension, drop down and use the low wind to reach our destination. If we time it well, and the wind doesn’t change direction(s), we should be able to land accurately at our destination.
Your problem is to write a program to calculate balloon flight plans. For simplicity we will assume that there are two wind directions that remain stable. The goal will be to calculate the fastest possible path or to determine that no path is possible. We will assume that we can raise and lower the balloon without moving significantly over the ground – as though the change in elevation was very rapid. However, we will add an artificial time penalty of 30 seconds to our time plan for every elevation change (either up or down), so that there is a disincentive to us changing elevation too often.
If this was sounding too easy, there is one complication. Air traffic control has restricted us to a flight corridor of width W centred on the straight line between our starting and target points. We are not permitted to fly outside this corridor. This means that we may have to follow some kind of zigzag path.
The input consists of a number of problems. The first line of the input holds one integer value (N) being the number of problems to solve. Each problem is specified on a single line of input with 9 floating point values: Sx, Sy (the x and y coordinates of the starting position in metres); Xx and Xy (the x and y coordinates of the target position in metres); Lx and Ly (the x and y coordinates of the low wind velocity vector in metres/sec); Hx and Hy (the x and y coordinates of the high wind velocity vector in metres/sec) and W (the width of the flight corridor in metres). You can assume that neither the Low nor the High wind ever blows exactly in the direction from S to X.
The output consists of one line per problem. The line either holds the word “Impossible” or is has the time required for the flight (including time penalties) in seconds, rounded to the nearest second
1 0 0 14000 14000 3 0 0 3 12000