// Verificador de "Una gira para muchos lugares": verificador ENTRADA ESPERADA SALIDA.
// En ESPERADA está A, el peso de la red más barata que conecta todos los lugares. El verificador lo
// recalcula. Comprueba que el recorrido pase una vez por cada lugar, que su largo, medido aquí, sea
// el que se escribió, que no pase de 2A y que ningún cambio de dos tramos lo acorte.
// Termina con 0 si todo está bien, con 1 y un mensaje si no, y con 2 si el caso está mal armado.
#include <algorithm>
#include <cmath>
#include <cstddef>
#include <cstdlib>
#include <fstream>
#include <iostream>
#include <limits>
#include <numbers>
#include <string>
#include <vector>

namespace {

struct Place {
    double latitude;
    double longitude;
};

[[noreturn]] void reject(const std::string& reason) {
    std::cout << reason << '\n';
    std::exit(1);
}

bool parse_number(const std::string& word, long long& value) {
    if (word.empty() || word.size() > 18) return false;
    value = 0;
    for (char c : word) {
        if (c < '0' || c > '9') return false;
        value = value * 10 + (c - '0');
    }
    return true;
}

long long distance_m(const Place& a, const Place& b) {
    const double to_radians = std::numbers::pi / 180.0;
    const double phi1 = a.latitude * to_radians;
    const double phi2 = b.latitude * to_radians;
    const double half_dphi = (phi2 - phi1) / 2.0;
    const double half_dlambda = (b.longitude - a.longitude) * to_radians / 2.0;
    const double h = std::sin(half_dphi) * std::sin(half_dphi) +
                     std::cos(phi1) * std::cos(phi2) * std::sin(half_dlambda) * std::sin(half_dlambda);
    return static_cast<long long>(std::ceil(2.0 * 6371000.0 * std::asin(std::sqrt(std::min(1.0, h)))));
}

long long spanning_weight(const std::vector<long long>& d, std::size_t n) {
    const long long INF = std::numeric_limits<long long>::max();
    std::vector<long long> best(n, INF);
    std::vector<char> inside(n, 0);
    if (n > 0) best[0] = 0;
    long long weight = 0;
    for (std::size_t round = 0; round < n; round++) {
        std::size_t v = n;
        for (std::size_t u = 0; u < n; u++) {
            if (inside[u] == 0 && (v == n || best[u] < best[v])) v = u;
        }
        inside[v] = 1;
        weight += best[v];
        for (std::size_t u = 0; u < n; u++) {
            if (inside[u] == 0) best[u] = std::min(best[u], d[v * n + u]);
        }
    }
    return weight;
}

}  // namespace

int main(int argc, char* argv[]) {
    if (argc != 4) reject("uso: verificador ENTRADA ESPERADA SALIDA");
    std::ifstream input(argv[1]);
    std::ifstream expected(argv[2]);
    std::ifstream output(argv[3]);

    std::size_t n = 0;
    input >> n;
    std::vector<Place> places(n);
    for (auto& place : places) {
        std::string name;
        input >> place.latitude >> place.longitude;
        std::getline(input, name);
    }
    std::vector<long long> d(n * n, 0);
    for (std::size_t i = 0; i < n; i++) {
        for (std::size_t j = i + 1; j < n; j++) d[i * n + j] = d[j * n + i] = distance_m(places[i], places[j]);
    }
    const long long network = spanning_weight(d, n);
    long long written = 0;
    expected >> written;
    if (written != network) {
        std::cout << "caso mal armado: el archivo dice " << written << " y el cálculo da " << network << '\n';
        return 2;
    }

    std::string word;
    long long length = 0;
    if (!(output >> word) || !parse_number(word, length)) reject("la primera palabra no es un largo válido");

    std::vector<std::size_t> tour;
    std::vector<char> seen(n, 0);
    for (std::size_t k = 0; k < n; k++) {
        long long place = 0;
        if (!(output >> word)) reject("faltan lugares en el recorrido");
        if (!parse_number(word, place)) reject("número de lugar inválido: " + word);
        if (place < 0 || place >= static_cast<long long>(n)) reject("lugar fuera de rango: " + word);
        const std::size_t v = static_cast<std::size_t>(place);
        if (seen[v] != 0) reject("el lugar " + word + " aparece dos veces");
        seen[v] = 1;
        tour.push_back(v);
    }
    if (output >> word) reject("sobra texto después del recorrido: " + word);

    long long measured = 0;
    for (std::size_t k = 0; k < n; k++) measured += d[tour[k] * n + tour[(k + 1) % n]];
    if (measured != length) reject("el recorrido mide " + std::to_string(measured) + ", no " + std::to_string(length));
    if (length > 2 * network) {
        reject("el largo " + std::to_string(length) + " pasa de 2A = " + std::to_string(2 * network));
    }

    // Cada par de tramos sin lugares en común: (a, a + 1) y (b, b + 1).
    for (std::size_t a = 0; a < n; a++) {
        for (std::size_t b = a + 2; b < n; b++) {
            if (a == 0 && b == n - 1) continue;
            const std::size_t p = tour[a];
            const std::size_t q = tour[a + 1];
            const std::size_t r = tour[b];
            const std::size_t s = tour[(b + 1) % n];
            const long long now = d[p * n + q] + d[r * n + s];
            const long long changed = d[p * n + r] + d[q * n + s];
            if (changed < now) {
                reject("se puede acortar: cambiar los tramos de las posiciones " + std::to_string(a) + " y " +
                       std::to_string(b) + " ahorra " + std::to_string(now - changed) + " m");
            }
        }
    }
    return 0;
}