| J. Diffusing Nuclear Bombs on Planet X |
In the year 30823245, a terrorist has planted n nuclear bombs on a planet, which we will refer to as planet X. You must diffuse all the bombs, by visiting all the bombs and returning to your starting position in the least amount of time possible. Planet X is modelled as an ellipsoid with axis a,b, and c (i.e., it is defined by the surface x2/a2+y2/b2+z2/c2=1). The surface consist of both land and bodies of water. Your traveling speed on land is different from that of water. Given your starting position, the positions of the nuclear bombs, your traveling speed on land and on water, terrain information which defines which areas are land and which are water, compute the shortest time it takes you to diffuse all bombs and return to your headquarter. All coordinates are given in longitudes, and latitudes in degrees. The latitude is measured along the axis of c, while the longitude is measured around the ellipse formed by axis of a and b. Use Newtonian physics in this problem (i.e., ignore relativistic effects, even if you travel at or above the speed of light).
There is at most 1001 inputs. Each input starts with
n a b c s_long s_lat w l
Under the constraint, n < 15, w+l < 1010, a+b+c < 105.
on a single line. n is the number of bombs. a,b,c are the axis of the ellipsoid, given in meters with at most 3 digits after the decimal. s_long,s_lat are the latitude and logitude of the starting position in degrees with at most 3 digits after the decimal. w is the speed on water, and l is the speed on land in meters per second with at most 3 digits after the decimal.
n lines follow describing each bomb. Each line has three floating point numbers,
lat long r
with at most 3 digits after the dicimal. lat long are the latitude and logitude of the bomb. r indicates that within a geodesic distance of r from the location of the bomb is completely land. The geodesic distance is the shortest distance on the surface of the ellipsoid. Any terrain that is not specified as land, is considered to be water.
For each input, output the least amount of time in seconds on a single line, rounded to 3 digits after the decimal.
3 100.000 100.000 200.000 0.000 0.000 1.0 2.0 20.000 30.000 3.000 40.000 20.000 3.000 10.000 10.000 3.000
367.843