#include <cstdlib>
#include <iostream>
#include <vector>
#include <fstream>
#include <cmath>

typedef struct coord{int abs; int ord;} coord;
void pointRandom(int n, coord point[]);
void distances(int n, int m, coord point[], int edge[][3]);
void tri(int m, int edge[][3]);
void affichageGraphique(int n, int m, coord point[], int arbre[][2],  const char * filename);
void kruskal (int n, int edge[][3], int arbre[][2]);
void fusion(int tableau[][3],int deb1,int fin1,int fin2);
void tri_fusion(int tableau[][3],int longueur);
void tri_fusion_bis(int tableau[][3],int deb,int fin);
using namespace std;

int
main()
{
  int n;             //Le nombre de points.
  cout << "Entrer le nombre de points: ";
  cin >> n;
  int m=n*(n-1)/2;   // Le nombre de paires de points.
  coord point[n];    // Les coordonnees des points dans le plan.
  int edge[m][3];    // Les paires de points et le carre de leur longueur.
  int arbre[n-1][2]; // Les aretes de l'arbre de Kruskal.
  pointRandom(n,point);
  distances(n,m,point,edge);
  tri(m,edge);
  for (int i =0; i < m; i ++){
    cout << "point "<< edge[i][0]<<":"<<edge[i][1]<<" coords : ("<< point[edge[i][0]].abs<<";"<<point[edge[i][0]].ord <<") ; ("<<point[edge[i][1]].abs<<" ; "<<point[edge[i][1]].ord<<") norme : "<<edge[i][2]<< endl;
  }
  int edge2[m][2];
  for(int i =0; i < m; i ++){
    edge2[i][0]=edge[i][0];
    edge2[i][1]=edge[i][1];
  }
  affichageGraphique(n,m, point,edge2, "graphe.ps");
  kruskal(n,edge,arbre);
  affichageGraphique(n,n-1,point,arbre, "arbre.ps");
  // system("evince graphe.ps");
  return EXIT_SUCCESS;
}

void pointRandom(int n, coord point[]){
    srand(time(NULL));
    for (int i =0; i < n; i ++){
      point[i].abs = rand()%612;
      point[i].ord =rand()%792;
      cout << "Created point "<<i<<" coords : "<< point[i].abs <<" : "<<point[i].ord<<endl;
    }
}

void distances(int n, int m, coord point[], int edge[][3]){
  int k = 0;
    for (int i =0; i < n; i ++){
      for(int j = i+1; j < n; j ++){
        edge[k][0]=i;
        edge[k][1]=j;
        edge[k][2]=(pow(point[j].abs-point[i].abs,2)+pow(point[j].ord-point[i].ord,2));
        k++;
      }
    }
    cout<<"calcul des distance : OK"<<endl;
}

void fusion(int tableau[][3],int deb1,int fin1,int fin2)
        {
        int table1[fin1-deb1+1][3];
        int deb2=fin1+1;
        int compt1=deb1;
        int compt2=deb2;
        int i;
        //on recopie les éléments du début du tableau
        for(i=deb1;i<=fin1;i++)
            {
            swap(table1[i-deb1],tableau[i]);
            }

        for(i=deb1;i<=fin2;i++)
            {
            if (compt1==deb2) //c'est que tous les éléments du premier tableau ont été utilisés
                {
                break; //tous les éléments ont donc été classés
                }
            else if (compt2==(fin2+1)) //c'est que tous les éléments du second tableau ont été utilisés
                {
                swap(tableau[i],table1[compt1-deb1]); //on ajoute les éléments restants du premier tableau
                compt1++;
                }
            else if (table1[compt1-deb1][2]<tableau[compt2][2])
                {
                swap(tableau[i],table1[compt1-deb1]); //on ajoute un élément du premier tableau
                compt1++;
                }
            else
                {
                swap(tableau[i],tableau[compt2]); //on ajoute un élément du second tableau
                compt2++;
                }
            }
        }

void tri_fusion_bis(int tableau[][3],int deb,int fin)
        {
        if (deb!=fin)
            {
            int milieu=(fin+deb)/2;
            tri_fusion_bis(tableau,deb,milieu);
            tri_fusion_bis(tableau,milieu+1,fin);
            fusion(tableau,deb,milieu,fin);
            }
        }

void tri_fusion(int tableau[][3],int longueur)
     {
     if (longueur>0)
            {
            tri_fusion_bis(tableau,0,longueur-1);
            }
     }
void tri(int m, int edge[][3]){
  for (int i = 0 ; i < m ; i ++){
    for(int j=i+1; j < m; j ++){
      if ( edge[i][2]>edge[j][2]){
        swap(edge[i][0],edge[j][0]);
        swap(edge[i][1],edge[j][1]);
        swap(edge[i][2],edge[j][2]);
      }
    }
  }
}

void affichageGraphique(int n, int m, coord point[], int arbre[][2], const char * filename)
// Cree le fichier Exemple.ps qui affiche
// les points et l'arbre de Kruskal.
{
  ofstream output;
  output.open(filename,ios::out);
  output << "%!PS-Adobe-3.0" << endl;
  output << "%%BoundingBox: 0 0 612 792" << endl;
  output << endl;
  for(int i=0;i<n;i++)
    {
      output << point[i].abs << " " << point[i].ord << " 3 0 360 arc" <<endl;
      output << "0 setgray" <<endl;
      output << "fill" <<endl;
      output << "stroke"<<endl;
      output << endl;
    }
  output << endl;
  for(int i=0;i<m;i++)
   {
     output << point[arbre[i][0]].abs << " " << point[arbre[i][0]].ord
	    << " moveto" << endl;
     output << point[arbre[i][1]].abs << " " << point[arbre[i][1]].ord
	    << " lineto" << endl;
     output << "stroke" << endl;
     output << endl;
   }
  output << "showpage";
  output << endl;
}

void kruskal (int n, int edge[][3], int arbre[][2]){
  int comp[n];
  int indicea=0;
  for(int i =0; i < n-1; i ++){
    arbre[i][0]=0;
    arbre[i][1]=0;
  }
  for (int i = 0; i < n; i ++){
    comp[i]=i;
  }
  for(int i = 0 ; i < n*(n-1)/2;i++ ){
    if ( comp[edge[i][0]]!=comp[edge[i][1]]){
      int aux = comp[edge[i][0]];
      arbre[indicea][0]=edge[i][0];
      arbre[indicea][1]=edge[i][1];
      for(int j = 0; j < n; j ++){
        if (comp[j]==aux){
          comp[j]=comp[edge[i][1]];
        }
      }
      indicea++;
    }
  }
}