# La gira más corta Un equipo de salud sale de una ciudad, visita una sola vez cada una de las otras y vuelve a la ciudad de partida. Tiene pocas ciudades y va a pagar cada kilómetro durante años, así que quiere **el recorrido más corto que existe**. No uno bueno: el mejor, y además saber cuál es. Las coordenadas de las capitales regionales están en [`capitales.csv`](../../capitales.csv), tomadas de GeoNames, con licencia CC BY 4.0. La fuente completa está en [`capitales.md`](../../capitales.md). Algunos casos usan esas ciudades, y otros, puntos ficticios. La distancia entre dos ciudades **no** es la de una carretera: es la del gran círculo, el camino más corto sobre una esfera de radio R = 6371 km. Se mide así, con la fórmula de haversine, con φ y λ en radianes: ```text h = sin²((φ₂ − φ₁) / 2) + cos φ₁ · cos φ₂ · sin²((λ₂ − λ₁) / 2) d = ⌈2 · R · arcsen(√h)⌉ con R = 6371000 metros ``` Es decir, en metros, redondeada **hacia arriba** al entero. Calculen con `double`. Entre Lima y Callao, en este caso, d = 11596 m. Como cada tramo es un entero, también lo es el largo de un recorrido, que es la suma de sus n tramos, incluido el que vuelve al inicio. Con n = 2 se va y se vuelve por el mismo tramo, así que se cuenta dos veces. ## Entrada La primera línea tiene n, la cantidad de ciudades. Siguen n líneas, una por ciudad, cada una con la latitud y la longitud en grados, y después el nombre, que puede tener espacios. Las ciudades se numeran de 0 a n − 1, en el orden en que aparecen. Dos ciudades pueden estar en el mismo punto, y entonces su distancia es 0. ## Salida - Una línea con el largo mínimo, en metros. - Una línea con los n números de las ciudades, en el orden en que se visitan. Se vuelve de la última a la primera sin escribirla otra vez. Puede empezar en cualquier ciudad y puede ir en cualquier sentido, porque hay varios recorridos correctos: un verificador revisa su respuesta. Comprueba que el largo sea el mínimo, que aparezca cada ciudad una vez y que el largo del recorrido escrito, medido de nuevo con la fórmula, sea el que ustedes dicen. ## Límites - 1 ≤ n ≤ 20 - −90 ≤ latitud ≤ 90, y −180 ≤ longitud ≤ 180, con 5 decimales a lo sumo - Memoria: 256 MiB ## Ejemplo Entrada: ```text 4 -12.04318 -77.02824 Lima -12.05162 -77.13452 Callao -12.06866 -75.21027 Huancayo -14.07538 -75.73422 Ica ``` Salida: ```text 710919 1 3 2 0 ``` El recorrido es Callao, Ica, Huancayo, Lima, y de vuelta a Callao. Medido en el otro sentido, o desde otra ciudad, también vale. ## Tiempo 2 segundos por caso, compilado con `-O2`. Corran `make test` para probar con el juez. El juez no mide la memoria. Para comprobarla por su cuenta, en bash, desde esta carpeta y con los casos ya armados por `make test` (`build/casos`): ```sh bash -c 'ulimit -v 262144; build/solution < build/casos/13.in' ``` Ese límite cuenta todo lo que el programa pide, en KiB: 262144 son 256 MiB. Si no le alcanza, el programa termina con error.