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

using namespace std;

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

typedef struct coord{int abs; int ord;} coord;
typedef struct point{int x; int y;} point;

void pointRandom(int n,coord point[][]);
float distancexy(coord p1,coord p2);
void voisins(int n,int dmax,coord point[][],vector<point> 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][N];                  // Les coordonnees des points.
  vector<point> voisin[N][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 < 10; i ++){
      for (int j = 0; j < 10; j ++){
      point[i][j].abs = 60*i;
      point[i][j].ord = 60*j;
      cout << "Created point "<<i<<","<<j<<" coords : "<< point[i][j].abs <<" : "<<point[i][j].ord<<endl;
      k++;
    }
    }
  }
float distancexy(point p1, point p2){
  return pow((abs(p2.x-p1.x)+abs(p2.y-p1.y)),2);
}
void voisins (int n, int dmax, coord point[][], vector<point> voisins[][], int &m){
  int arrete = 0;
  for (int i = 0; i < 10; i ++){
    for (int j = 0; j < 10; j ++){
      for (int o = 0; o < 10 ; o ++){
        for (int k = 0; k < 10; k ++){
          if (((o==i+1) && (j==k))|| ((k==j+1) && (i==o)) || ((o==i+1) && (k==j+1))){
            point tmp;
            tmp.x=o;
            tmp.y=k;
            voisins[i][j].push_back(tmp);
            tmp.x=i;
            tmp.y=j;
            voisins[o][k].push_back(tmp);
          }
        }
      }
      }
    }
  }
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<10;i++)
  for (int j = 0 ; j < 10; j ++){
    {
      output << point[i][j].abs << " " << point[i][j].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<10;i++)
   {
     for (int k =0; k < 10; k ++){
     for (int j =0; j < voisins[i][k].size(); j ++){

         output << point[voisin[i][k][j].x][voisin[i][k][j].y].abs<<" "<<point[voisin[i][k][j].x][voisin[i][k][j].y].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;
}