# Una gira para muchos lugares

Una empresa reparte vacunas por cientos de lugares. Sale de un lugar, pasa una sola vez por cada uno y vuelve al inicio.
Ya no le hace falta el recorrido más corto que existe, que nadie va a poder calcular con tantos lugares a tiempo. Le basta
un recorrido que cumpla dos condiciones, y que las pueda comprobar cualquiera:

1. **Que tenga un tope.** Sea A el menor largo total de un conjunto de tramos que deje conectados a todos los lugares, de
   modo que de cada uno se pueda llegar a cualquier otro pasando por esos tramos. El largo del recorrido no debe pasar de 2A.
2. **Que no se pueda arreglar a la vista.** Tomen dos tramos del recorrido que no tengan lugares en común, de a hacia b y de
   c hacia d, con el recorrido escrito en este orden: a, b, …, c, d, …. Si cambiamos esos dos tramos por los de a hacia c y
   de b hacia d, recorriendo lo de en medio al revés, sale otro recorrido. Ninguno de esos cambios debe acortarlo.

Hay casos con las capitales regionales, de [`capitales.csv`](../../capitales.csv), tomadas de GeoNames, con licencia CC BY
4.0, y la fuente completa en [`capitales.md`](../../capitales.md). Otros usan lugares ficticios.

La distancia entre dos lugares **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.

## Entrada

La primera línea tiene n, la cantidad de lugares. Siguen n líneas, una por lugar, cada una con la latitud y la longitud en
grados, y después el nombre, que puede tener espacios. Los lugares se numeran de 0 a n − 1, en el orden en que aparecen.
Dos lugares pueden estar en el mismo punto, y entonces su distancia es 0.

## Salida

- Una línea con el largo del recorrido, en metros.
- Una línea con los n números de los lugares, en el orden en que se visitan. Se vuelve del último al primero sin
  escribirlo otra vez.

Puede haber muchos recorridos correctos: un verificador revisa su respuesta. Comprueba que aparezca cada lugar una vez, que
el largo, medido de nuevo con la fórmula, sea el que ustedes dicen, y las dos condiciones.

## Límites

- 1 ≤ n ≤ 1500
- −90 ≤ latitud ≤ 90, y −180 ≤ longitud ≤ 180, con 5 decimales a lo sumo
- Memoria: 256 MiB

## Ejemplo

Entrada:

```text
5
-12.04318 -77.02824 Lima
-12.05162 -77.13452 Callao
-12.06866 -75.21027 Huancayo
-13.53188 -71.96701 Cusco
-16.39899 -71.53747 Arequipa
```

Salida:

```text
1691829
0 1 4 3 2
```

El orden de la entrada, `0 1 2 3 4`, mide 1695072 m y no cumple la condición 2: cambiar los tramos Callao-Huancayo y
Arequipa-Lima por Callao-Arequipa y Huancayo-Lima lo acorta. En este ejemplo A = 918911 m, así que 2A = 1837822 m, y la salida no pasa de ahí.

## 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 > /dev/null'
```

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.