Problem G
Flygskam
To calculate the best route you models the planet as a perfect sphere and assumes that all flights fly at the distance $6381$ km from the center of the earth. The amount of shame for a single point-to-point flight is calculated as the distance between the airports in km, plus a take-off and landing penalty of $100$, that is, two airports with the flight distance $1000$ km will result in $1100$ shame.
Latitude and longitude
The positions of the airports are given as the latitude and longitude in (decimal) degrees. The latitude of a point $P$ on the earths surface is the angle between the equatorial plane and a line passing through $P$ and the center of the earth. The equator has latitude $0^\circ $, points north of the equator has positive values and points south of the equator has negative values, the North Pole has latitude $90^\circ $ and the South Pole latitude $-90 ^\circ $. Half circles that run from the North to the South pole are called meridians. The zero meridian runs through Greenwich. The longitude of a point $Q$ is the angle between the zero meridian plane and the line that run through $Q$ and the center of the earth, with values from $- 180^\circ $ to $+180^\circ $, with positive values east of Greenwich.
Input
Input starts with one line with two integers $1 \leq N \leq 10\, 000$, the number of airports and $1 \leq M \leq 100\, 000$, the number of two-way flight routes. The second line has two strings $S$ and $T$, Skylar’s start position and Skylar’s target position. Then follows $N$ lines, each starts with a three letter (uppercase) airport code, followed by two real values numbers, the latitude and longitude in degrees. Then follows $M$ lines, each with two strings $a$ and $b$, the airports with a two-way flight connection.
All flight airports have unique names and all connections are between existing airports.
Output
Output a real value with the minimum amount of flygskam Skylar will obtain on a one-way trip. If the target is unreachable and Skylar will be forever alone, output -1. Answers within a relative or absolute error of $10^{-6}$ will be accepted.
| Sample Input 1 | Sample Output 1 |
|---|---|
4 4 ARN SCR ARN 59.6467921 17.9370443 SCR 61.156603 12.837360 CPH 55.618023 12.650763 OSL 60.197646 11.100008 ARN OSL ARN CPH SCR OSL OSL CPH |
729.09706162045 |
| Sample Input 2 | Sample Output 2 |
|---|---|
2 1 LAX AKL AKL -37.006131 174.783781 LAX 33.941589 -118.408531 LAX AKL |
10603.3297338597 |
| Sample Input 3 | Sample Output 3 |
|---|---|
4 2 CDG AKL AKL -37.006131 174.783781 CDG 49.014490 2.542102 DXB 25.253176 55.365673 LAX 33.941589 -118.408531 CDG LAX DXB AKL |
-1 |
