// Distancias entre lugares de la Tierra. El gran círculo es el camino más corto por la superficie
// de una esfera de radio 6371 km: no es una carretera ni una ruta aérea real.
// Cada distancia se guarda en metros enteros, redondeada hacia arriba.
#pragma once
#include <algorithm>
#include <cmath>
#include <cstddef>
#include <fstream>
#include <numbers>
#include <stdexcept>
#include <string>
#include <vector>

namespace geo {

inline constexpr double EARTH_RADIUS_M = 6371000.0;

struct Place {
    std::string name;
    double latitude;
    double longitude;
};

using Matrix = std::vector<std::vector<long long>>;

inline std::size_t at(int i) { return static_cast<std::size_t>(i); }

// La fórmula de haversine, en metros. Se porta bien con puntos muy cercanos.
inline double great_circle_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 2.0 * EARTH_RADIUS_M * std::asin(std::sqrt(std::min(1.0, h)));
}

inline long long distance_m(const Place& a, const Place& b) {
    return static_cast<long long>(std::ceil(great_circle_m(a, b)));
}

// Lo que ocurre si se tratan los grados como un plano: una mala distancia, a propósito.
inline long long flat_m(const Place& a, const Place& b) {
    const double dlat = a.latitude - b.latitude;
    const double dlon = a.longitude - b.longitude;
    const double metres_per_degree = EARTH_RADIUS_M * std::numbers::pi / 180.0;
    return static_cast<long long>(std::ceil(std::sqrt(dlat * dlat + dlon * dlon) * metres_per_degree));
}

inline Matrix distance_matrix(const std::vector<Place>& places) {
    const int n = static_cast<int>(places.size());
    Matrix d(at(n), std::vector<long long>(at(n), 0));
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            d[at(i)][at(j)] = d[at(j)][at(i)] = distance_m(places[at(i)], places[at(j)]);
        }
    }
    return d;
}

// Lee capitales.csv: una cabecera y luego nombre,latitud,longitud.
inline std::vector<Place> read_places(const std::string& path) {
    std::ifstream file(path);
    if (!file) throw std::runtime_error("no se pudo abrir " + path);
    std::vector<Place> places;
    std::string line;
    std::getline(file, line);
    while (std::getline(file, line)) {
        const std::size_t first = line.find(',');
        const std::size_t second = line.find(',', first + 1);
        places.push_back({line.substr(0, first), std::stod(line.substr(first + 1, second - first - 1)),
                          std::stod(line.substr(second + 1))});
    }
    return places;
}

// Las primeras n filas del archivo.
inline std::vector<Place> first_places(const std::vector<Place>& places, int n) {
    return {places.begin(), places.begin() + n};
}

}  // namespace geo