#include <cstdlib>
#include <iostream>
#include <vector>
#include <fstream>
#include <math.h>
using namespace std;


		
const int n=4000;               // Le nombre de points.
const int dmax=20;		// La distance jusqu'a laquelle on relie deux points.
vector<int> voisin[n];          // Les listes de voisins.                    
int point[n][2];                // Les coordonnees des points.
int arbre[n-1][2];              // Les aretes de l'arbre de Dijkstra .
int pere[n];    		// La relation de filiation de l'arbre de Dijkstra.

  


void afficheGraphe(int n,int d, int sommet[][2])       
  {ofstream output;             // Cree le fichier Graphe.ps qui affiche le graphe.
  output.open("Graphe.ps",ios::out);
  output << "%!PS-Adobe-3.0" << endl;
  output << endl;  
  for(int i=0;i<n;i++)
    {output << sommet[i][0] << " " << sommet[i][1] << " 1 0 360 arc" <<endl;
    output << "0 setgray" <<endl;
    output << "fill" <<endl;
    output << "stroke"<<endl;
    output << endl;
    }
  output << endl;
  for(int i=0;i<n-1;i++)
    {for (int j=i+1 ;j<n;j++)
      if ((sommet[i][0]-sommet[j][0])*(sommet[i][0]-sommet[j][0])+
	(sommet[i][1]-sommet[j][1])*(sommet[i][1]-sommet[j][1])<d*d)
      {output << sommet[i][0] << " " << sommet[i][1] 
      << " moveto" << endl;
      output << sommet[j][0] << " " << sommet[j][1] 
      << " lineto" << endl;
      output << "stroke" << endl;
      output << endl;
      }
    }
  }

void afficheArbre(int n, int k, int point[][2], int arbre[][2])  
// Cree le fichier Arbre.ps qui affiche l'arbre.
{ofstream output;                           
 output.open("Arbre.ps",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][0] << " " << point[i][1] << " 1 0 360 arc" <<endl;
   output << "0 setgray" <<endl;
   output << "fill" <<endl;
   output << "stroke"<<endl;
   output << endl;
   }
 output << endl;
 for(int i=0;i<k;i++)
   {output << point[arbre[i][0]][0] << " " << point[arbre[i][0]][1] 
	   << " moveto" << endl;
   output << point[arbre[i][1]][0] << " " << point[arbre[i][1]][1] 
	  << " lineto" << endl;
   output << "stroke" << endl;
   output << endl;
   }
output.close();
}