eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

The Flight Way

The Flight Way

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

Club of obsolete vehicles decided to celebrate the May 5th, 5555 with great flights of copies of ancient air planes. Club members have built in various places on the Earth surface N (2N1000) aerodromes and prepared planes. But suddenly an amendment to the ecological taxes law was adopted, so the club must hold the celebrations in short format. Two aerodromes were selected, and the only one plane will fly between them using the shortest possible way! The maximum distance it can fly without landings is R km, so if necessary it can use intermediate aerodromes.

Help the club to find the shortest route, considering the Earth surface accurate sphere with equator length exactly 40000 km and ignoring the influence of flying height at the distance.

Вхідні дані

The first row of the input contains R – the maximum direct fly distance (in kilometers, 10R50000). The second row contains the number of aerodromes N. The following N rows contain geographic coordinates of the aerodromes. The format of coordinates is: first the latitude (uppercase letter N or S — North or South, then degrees, minutes and seconds), then longitude (similarly, but using the letter E or W — East or West), all numbers and letters are separated by single space. Degrees and minutes are integers, seconds can have decimal fractions. At the last line of the input, two integers denotes the aerodromes selected as start and finish (1-based, i. e. numeration starts from 1).

Вихідні дані

Your program should output three lines. The 1st line should contain one floating-point value — the minimal possible length of route from start to finish, in kilometers, with accuracy up to meters. The 2nd line should contain exactly one integer K — the number of intermediate aerodromes in the route. The 3rd line should contain list of these intermediate aerodromes, in order from start to finish. If there are different correct answers, your program should find any one of them. If plane can reach finish from start without landings, the 2nd line should contain 0 and the 3rd line should be empty. If plane cannot reach finish from start, the 1st line must contain number 123456789.000, the 2^nd — number 0 and the 3rd should be empty

Приклад

Вхідні дані #1
7127
5
N 90 0 0 E 0 0 0
N 0 0 0 W 15 0 0
S 90 0 0 E 0 0 0
N 30 0 0 E 175 0 0
S 30 0 0 W 175 0 0
1 3
Вихідні дані #1
20083.446
2
4 5
Джерело International Collegiate Programming Contest, Ukraine, Quarter-Final,May 19, 2011