```/*************************************************************************************************************************************/
/*                                                                                                                                   */
/*        M A X I M I S A T I O N   D E   L A   P L U S   P E T I T E   D I S T A N C E                                              */
/*        A   L ' I N T E R I E U R   D ' U N   N U A G E   D E   P O I N T S                                                        */
/*        P A R   U N E   M E T H O D E   D U   T Y P E   " R E C U I T   S I M U L E "  :                                           */
/*                                                                                                                                   */
/*                                                                                                                                   */
/*        Author of '\$xtc/recuit_si.32\$c' :                                                                                          */
/*                                                                                                                                   */
/*                    Jean-Francois Colonna (LACTAMME, AAAAMMJJhhmmss).                                                              */
/*                                                                                                                                   */
/*************************************************************************************************************************************/

#include  "INCLUDES.01.I"
/* Introduit le 20051116102150...                                                            */

extern    void      *malloc();

static    int       dimX=0;
#define   Xmin      0
#define   Xmax      (Xmin + (dimX-1))
/* Definition des abscisses.                                                                 */
static    int       dimY=0;
#define   Ymin      0
#define   Ymax      (Ymin + (dimY-1))
/* Definition des ordonnees.                                                                 */

#define   IMAGE(x,y)                                                                                                                    \
(*(image + (((((int)y)-Ymin)*dimX) + (((int)x)-Xmin))))                                                             \
/* Acces a un point de l'image.                                                              */
#define   store(n,x,y)                                                                                                                  \
{                                                                                                                   \
IMAGE(x,y) = n;                                                                                                     \
}                                                                                                                   \
/* Rangement d'un point valide d'une image.                                                  */

#define   nPOINTS                                                                                                                       \
20                                                                                                                  \
/* Nombre de points du nuage...                                                              */
#define   nITERATIONS                                                                                                                   \
100000                                                                                                              \
/* Nombre d'iterations maximum...                                                            */

#define   DELTA                                                                                                                         \
5.0                                                                                                                 \
/* Plus grande variation possible des coordonnees {x,y}.                                     */

#define   PROBABILITE_D_ACCEPTATION_D_UNE_MAUVAISE_SOLUTION                                                                             \
0.0                                                                                                                 \
/* Probabilite d'accepter une mauvaise solution...                                           */

extern    double    drand48();
#define   ALEA                                                                                                                          \
((drand48() - 0.5)*DELTA)                                                                                           \
/* Plus grande variation possible des coordonnees {x,y}, en rappelant que :                  */ \
/*                                                                                           */ \
/*                  drand48() E [0,1]                                                        */ \
/*                                                                                           */ \
/* d'ou la translation de 0.5 qui permet d'avoir un deplacement algebrique :                 */ \
/*                                                                                           */ \
/*                  ALEA E [-0.5,+0.5]                                                       */ \
/*                                                                                           */ \
/* ce qui permet de se mouvoir dans n'importe quelle direction...                            */
extern    double    sqrt();

typedef   struct    point     {
double    x;
double    y;
}         point;
/* 'struct' de definition d'un point...                                                      */

#define   X(P)                                                                                                                          \
(P.x)
#define   Y(P)                                                                                                                          \
(P.y)
/* Definition de l'acces aux coordonnees d'un point.                                         */

#define   MINI(a,b)                                                                                                                     \
(((a) < (b)) ? (a) : (b))                                                                                           \
/* Definition de la recherche du minimum.                                                    */
#define   MAXI(a,b)                                                                                                                     \
(((a) > (b)) ? (a) : (b))                                                                                           \
/* Definition de la recherche du maximum.                                                    */
#define   Carre(x)                                                                                                                      \
((x)*(x))                                                                                                           \
/* Definition du carre de 'x'.                                                               */

#define   d(A,B)                                                                                                                        \
sqrt(Carre(X(B)-X(A)) + Carre(Y(B)-Y(A)))                                                                           \
/* Definition de la distance entre deux points 'A' et 'B'.                                   */

#define   PROBABILITE_DE_PERTURBER_UN_POINT                                                                                             \
0.1                                                                                                                 \
/* Probabilite de perturber le point courant...                                              */

#define   PERTURBATION(coordonnee,minimum,maximum)                                                                                      \
{                                                                                                                   \
int       perturber=1;                                                                                              \
double    coordonnee_perturbee;                                                                                     \
\
if        (drand48() < PROBABILITE_DE_PERTURBER_UN_POINT)                                                           \
{                                                                                                         \
while     (perturber == 1)                                                                                \
{                                                                                               \
coordonnee_perturbee = coordonnee + ALEA;                                                       \
/* Perturbation de la coordonnee courante...                                                 */ \
\
if        ((coordonnee_perturbee < minimum) || (coordonnee_perturbee > maximum))                \
{                                                                                     \
/* Les coordonnees hors-ecran sont rejetees...                                               */ \
}                                                                                     \
else                                                                                            \
{                                                                                     \
coordonnee = coordonnee_perturbee;                                                    \
perturber=0;                                                                          \
/* On s'arrete sur la premiere coordonnee perturbee situee dans l'ecran...                   */ \
}                                                                                     \
}                                                                                               \
}                                                                                                         \
else                                                                                                                \
{                                                                                                         \
}                                                                                                         \
}

#define   DISTANCE_MINIMALE(distance_minimale)                                                                                          \
{                                                                                                                   \
distance_minimale=+1e+300;                                                                                          \
\
for       (i=0 ; i<nPOINTS ; i++)                                                                                   \
{                                                                                                         \
for       (j=0 ; j<nPOINTS ; j++)                                                                         \
{                                                                                               \
if        (i > j)                                                                               \
{                                                                                     \
double    distance_courante=d(Lpoints[i],Lpoints[j]);                                 \
distance_minimale=MINI(distance_minimale,distance_courante);                          \
/* Recherche de la distance minimale courante du nuage de points...                          */ \
}                                                                                     \
else                                                                                            \
{                                                                                     \
}                                                                                     \
}                                                                                               \
}                                                                                                         \
}

main()
{
int                 generer_les_positions_finales=0;
/* Pour controler la generation des positions finales uniquement (=1) ou des positions       */
/* finales et intermediaires (=0).                                                           */
int                 sortir_l_image=1;
/* Pour controler la sortie (=1) ou pas (=0) de l'image...                                   */
int                 x,y;
/* Definition des coordonnees.                                                               */
unsigned  char      *image;
/* Definition de l'image a generer...                                                        */

int       i,j,n;
int       iterations;
/* Index divers...                                                                           */
point     Lpoints[nPOINTS];
point     SLpoints[nPOINTS];
/* Liste des points et sa Sauvegarde.                                                        */
double    distances[nPOINTS][nPOINTS];
/* Matrice des distances.                                                                    */

Get(dimX,"dimX");
Get(dimY,"dimY");
/* Recuperation des dimensions en 'X' et en 'Y' de l'image a generer.                        */

image=malloc(dimY*dimX);
/* Definition de l'image a generer...                                                        */

for  (y=Ymin ; y<=Ymax ; y++)
{
for  (x=Xmin ; x<=Xmax ; x++)
{
store(NOIR,x,y);
/* Initialisation de l'image a generer...                                                    */
}
}

for       (n=0 ; n<nPOINTS ; n++)
{
X(Lpoints[n]) = drand48()*dimX;
Y(Lpoints[n]) = drand48()*dimY;
/* Initialisation arbitraire des points...                                                   */
}

for       (iterations=1 ; iterations<=nITERATIONS ; iterations++)
{
double    distance_minimale_avant;
double    distance_minimale_apres;

for       (n=0 ; n<nPOINTS ; n++)
{
X(SLpoints[n]) = X(Lpoints[n]);
Y(SLpoints[n]) = Y(Lpoints[n]);
/* Sauvegarde de l'etat courant des points...                                                */
}

DISTANCE_MINIMALE(distance_minimale_avant);
/* Recherche de la distance minimale avant la perturbation.                                  */

if        (iterations == 1)
{
fprintf(stderr,"distance minimale initiale=%f\n",distance_minimale_avant);
}
else
{
}

for       (n=0 ; n<nPOINTS ; n++)
{
double    X_perturbe=X(Lpoints[n]);
double    Y_perturbe=Y(Lpoints[n]);

PERTURBATION(X_perturbe,Xmin,Xmax);
PERTURBATION(Y_perturbe,Ymin,Ymax);

X(Lpoints[n]) = X_perturbe;
Y(Lpoints[n]) = Y_perturbe;
/* Perturbation aleatoire des points (sauf les deux premiers P0 et P1).                      */
}

DISTANCE_MINIMALE(distance_minimale_apres);
/* Recherche de la distance minimale apres la perturbation.                                  */

if        (    (distance_minimale_apres <= distance_minimale_avant)
||   (drand48() < PROBABILITE_D_ACCEPTATION_D_UNE_MAUVAISE_SOLUTION)
)
/* On cherche a maximiser la distance minimale...                                            */
{
for       (n=0 ; n<nPOINTS ; n++)
{
X(Lpoints[n]) = X(SLpoints[n]);
Y(Lpoints[n]) = Y(SLpoints[n]);
/* Restauration de l'etat anterieur lorsqu'il y a degradation des performances...            */
}
}
else
{
/* On conserve un etat perturbe qui maximise la distance minimale...                         */
}

if        (generer_les_positions_finales == 1)
{
}
else
{
for       (n=0 ; n<nPOINTS ; n++)
{
store(MAXI(NOIR+1,(BLANC*iterations)/nITERATIONS),X(Lpoints[n]),Y(Lpoints[n]));
/* Marquage des points...                                                                    */
}
}

if        (iterations == nITERATIONS)
{
fprintf(stderr,"distance minimale finale..=%f\n",distance_minimale_avant);
/* ATTENTION : c'est la distance minimale a l'avant-derniere iteration qui est editee car,   */
/* en effet, il n'est pas sur que 'distance_minimale_apres' etait maximale...                */
}
else
{
}
}

if        (generer_les_positions_finales == 1)
{
for       (n=0 ; n<nPOINTS ; n++)
{
store(BLANC,X(Lpoints[n]),Y(Lpoints[n]));
/* Marquage des points...                                                                    */
}
}
else
{
}

if        (sortir_l_image == 1)
{
write(1,image,dimX*dimY);
/* Sortie de l'image...                                                                      */
}
else
{
}
}
```