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

using namespace std;

const int N=1400;
const int M=(N*(N-1))/2;

typedef struct coord{int abs; int ord;} coord;

void pointRandom(int n,coord point[]);
float distancexy(coord p1,coord p2);
void voisins(int n,int dmax,coord point[],vector<int> voisin[],int &m);
void voisins2arete(int n,vector<int>voisins[],int arete[][2]);
void affichageGraphique(int n,int m,coord point[],vector<int> voisins[],const char * name);
bool existe(int n,int dis[],bool traite[]);
int searchsmallest(int n, int dist[],bool traite[]);
void dijkstra(int n,vector<int> voisin[],coord point[],int pere[], int m);
int construireArbre(int n,vector<int> voisin[],int pere[]);

int
main()
{
  int n;                           // Le nombre de points.
  cout << "Entrer le nombre de points: ";
  cin >> n;
  int dmax=50;                     // La distance jusqu'a laquelle on relie deux points.
  coord point[N];                  // Les coordonnees des points.
  vector<int> voisin[N];
  vector<int> voisinbis[N];           // Les listes de voisins.
  int arbre[N-1][2];               // Les aretes de l'arbre de Dijkstra.
  int pere[N];                     // La relation de filiation de l'arbre de Dijkstra.
  int m;                           // Le nombre d'aretes
  int arete[M][2];                 // Les aretes du graphe
  pointRandom(n,point);
  voisins(n,dmax, point, voisin, m);
  const char * filename = "affichage.ps";
  affichageGraphique(n,m,point,voisin,filename);
  cout<<"Graphe de base créé et exporté vers "<<filename<<endl;
  dijkstra(n,voisin,point,pere,m);
  construireArbre(n,voisinbis,pere);
  const char * filename2 = "affichagefin.ps";
  affichageGraphique(n,m,point,voisinbis,filename2);

  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;
    }
}
float distancexy(coord p1,coord p2){
  return sqrt((pow(p1.abs-p2.abs,2)+pow(p1.ord-p2.ord,2)));
}
void voisins (int n, int dmax, coord point[], vector<int> voisins[], int &m){
  int arrete = 0;
  for (int i = 0; i < n; i ++){
    for (int j = i+1; j < n; j ++){
      if ( sqrt(pow(point[i].abs-point[j].abs,2)+pow(point[i].ord-point[j].ord,2))<=dmax){
        voisins[i].push_back(j);
        voisins[j].push_back(i);
        arrete++;
      }
    }
  }
  m=arrete;
}

void affichageGraphique(int n, int m, coord point[], vector<int> voisins[], 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<n;i++)
   {
     for (int j =0; j < voisins[i].size(); j ++){
       if (voisins[i][j] >= i){
         output << point[i].abs<<" "<<point[i].ord << " moveto"<<endl;
         output<<point[voisins[i][j]].abs << " " << point[voisins[i][j]].ord << " lineto"<<endl;
         output<< "stroke"<<endl;
         output << endl;
       }
     }
   }
     output<<"showpage";
     output<<endl;
}
bool existe(int n,int dis[],bool traite[]){
  bool test = true;
  bool ret = false;
  int i = 0;
  while (test && i < n){
    if (!traite[i] && (dis[i]!=-1)){
      test = false;
      ret = true;
    }
    i++;
  }
  return ret;
}
int searchsmallest(int n, int dist[],bool traite[]){
  int ret=-1;
  int retdist = 10000;
  for (int i = 0 ; i < n; i ++){
    // cout<<"i :"<< i << " Dist de i "<< dist[i]<<" traite de i "<<traite[i]<<endl;
    if (traite[i]==false){
      if (dist[i]!= -1){
        if (dist[i]<=retdist){
          retdist=dist[i];
          ret =i;
        }
      }
    }
  }
  // cout<<"Lancment du traitement de :" << ret<<endl;
  return ret;
}
void dijkstra(int n, vector<int> voisin[], coord point[], int pere[], int m){
  int d[n];
  bool traite[n];
  for (int i =0; i < n; i ++){
    d[i]= -1;
    traite[i]=false;
  }
  pere[0]=0;
  d[0]=0;
  while (existe(n,d,traite)){
    int current = searchsmallest(n,d,traite);
    //cout<<"C'est ti-par avec current = "<< current <<endl;
    traite[current]=true;
    // cout<<"traite current : " << traite[current]<<endl;
    for (int i =0; i < voisin[current].size();i ++){
      int x = current;
      int y = voisin[current][i];
      //cout<<"Traitement de l'arete "<<x<<";"<<y<<endl;
      //cout << d[y] << "versus " << d[x]<< " + " <<distancexy(point[x],point[y])<<endl;
      if (!traite[y] && ((d[y]==-1) || (d[y]>(d[x]+distancexy(point[x],point[y]))))){
        d[y]=d[x]+distancexy(point[x],point[y]);
        pere[y]=x;
      }
    }
  }
}
int construireArbre(int n,vector<int> voisin[],int pere[]){
  for ( int i = 0; i < n; i ++){
    voisin[i].push_back(pere[i]);
    voisin[pere[i]].push_back(i);
  }
  return n;
}