# Mars Buggy

Mars is our neighbor in the solar system, about 1.5 times as far from the sun as the earth. In the past years we have seen several unmanned expeditions to the planet, some more succesful than others. The surface of Mars (picture: http://www.marsbase.net/m/mars-map.php) Imagine some time in the (near) future when Mars is colonised with several settlements scattered around the globe. Each settlement is equiped with a large array of solar panels and batteries to supply the energy needs of its inhabitants. Transport between the settlements is maintained by electric buggies that deliver people and goods around the planet. The range of these buggies is limited by the capacity of their battery and the payload they carry. To go from one place to the other, they may have to go from settlement to settlement, recharging the battery for every interval. The Problem You are hired by the Mars Public Transportation System (MPTS) to write their route planning software. Based on a list of settlements, the program should process transportation request for individ- ual buggies and print a list of intermediate settlements where the buggy will recharge. Each interval along the trip should, of course, be shorter or equal to the range of the particular buggy, but within that restriction the total length of the trip should be as short as possible. In case it is impossible to make the trip with a buggy with the given range, the program should calculate the minimum range a buggy should have to make the trip. The Facts For this problem we’ll consider Mars to be a perfectly flat sphere with a radius of 3390 kilometer. Places on Mars are localised by giving their latitude and longitude in radians. The northpole is at latitude π/2, the equator has latitude 0 and the southpole is at latitude −π/2. Longitude is given from east to west with a value from 0 to 2π, starting at an arbitrary meridian called the zero-meridian. Between two places a buggy will always take the shortest possible route, that is along a great circle. MPTS identifies settlements with a unique string of upto 20 characters, the location code. Legal characters for a location code are: upper- and lowercase letters, digits and the underscore; space characters are not allowed. For every settlement the location of the MPTS transfer station is listed by