// Agrupar con máxima separación: ocho puntos en el plano. El peso de cada arista es la
// distancia al cuadrado, un entero, que ordena igual que la distancia.
#include <iostream>
#include <string>
#include <vector>

#include "digraph.h"
#include "mst.h"

namespace {

struct Point {
    int x;
    int y;
};

std::vector<Edge> complete_graph(const std::vector<Point>& points) {
    std::vector<Edge> edges;
    int n = static_cast<int>(points.size());
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int dx = points[i].x - points[j].x;
            int dy = points[i].y - points[j].y;
            edges.push_back({i, j, dx * dx + dy * dy});
        }
    }
    return edges;
}

}  // namespace

int main() {
    std::vector<Point> points = {{0, 0}, {0, 2}, {2, 1}, {10, 0}, {11, 2}, {12, 0}, {5, 9}, {6, 10}};
    int n = static_cast<int>(points.size());
    std::vector<Edge> edges = complete_graph(points);

    std::cout << "Puntos:";
    for (int i = 0; i < n; i++) {
        std::cout << " " << i << "=(" << points[i].x << "," << points[i].y << ")";
    }
    std::cout << "\n\nÁrbol de expansión mínima, de la arista más barata a la más cara:\n ";
    for (const Edge& e : sorted_by_weight(kruskal(n, edges))) {
        std::cout << " " << e.u << "-" << e.v << ":" << e.weight;
    }
    std::cout << "\n\n";

    for (int k = 2; k <= 4; k++) {
        std::vector<int> group = max_spacing_groups(n, edges, k);
        long long partitions = 0;
        int best = best_spacing_brute(n, edges, k, &partitions);
        std::cout << "k = " << k << ": " << groups_text(group) << "\n";
        std::cout << "  separación " << spacing(edges, group) << ", fuerza bruta " << best << " entre " << partitions
                  << " particiones\n";
    }

    std::vector<Edge> sorted = sorted_by_weight(edges);
    sorted.resize(sorted.size() - 2);
    std::cout << "\nIdea que falla, k = 3: quitar las 2 aristas más caras del grafo completo\n";
    std::cout << "  quedan " << count_components(n, sorted) << " grupo\n";
}