#include <stdio.h>
#include <math.h>
#include <time.h>

struct data {
  double x;
  double y;
};

#define MAX 100
#define PNT 10
void gen(struct data d[], int n) {
  int i;
  for (i = 0; i < n; i++) {
    d[i].x = (double)(rand() % (MAX * PNT)) / PNT;
    d[i].y = (double)(rand() % (MAX * PNT)) / PNT;
  }
}

#define N 11
int next(int p[]) {
  int i, j, t;
  i = N - 2;
  p[0] = 0;
  while (p[i] >= p[i + 1])
    i--;
  if (i == 0)
    return 0;
  j = N - 1;
  while (p[i] >= p[j])
    j--;
  t = p[i];
  p[i] = p[j];
  p[j] = t;
  i++;
  j = N - 1;
  while (i < j) {
    t = p[i];
    p[i] = p[j];
    p[j] = t;
    i++;
    j--;
  }
  return 1;
}

double len(struct data d[], int p[], int n) {
  double sum, dx, dy;
  int i;
  sum = 0.0;
  for (i = 1; i < N; i++) {
    dx = fabs(d[p[i - 1]].x - d[p[i]].x);
    dy = fabs(d[p[i - 1]].y - d[p[i]].y);
    sum += sqrt(dx * dx + dy * dy);
  }
  dx = fabs(d[p[N - 1]].x - d[p[0]].x);
  dy = fabs(d[p[N - 1]].y - d[p[0]].y);
  sum += sqrt(dx * dx + dy * dy);
  return sum;
}

#define SEED 31415926
int main() {
  struct data d[N];
  int p[N], q[N];
  int i;
  double min, l;
  time_t t1, t2;
  srand(SEED);
  gen(d, N);
  for (i = 0; i < N; i++)
    printf("%d:(%4.1f, %4.1f)\n", i, d[i].x, d[i].y);

  t1 = time(NULL);
  for (i = 0; i < N; i++)
    p[i] = i;
  min = len(d, p, N);
  for (i = 0; i < N; i++)
    q[i] = p[i];
  do {
    l = len(d, p, N);
    if (l < min) {
      min = l;
      for (i = 0; i < N; i++)
        q[i] = p[i];
    }
  } while (next(p));
  t2 = time(NULL);

  for (i = 0; i < N; i++)
    printf("(%d)", q[i]);
  printf("\nmin = %.2f\n time: %d sec", min, t2 - t1);
  return 0;
}
/* end */

0:(11.1, 55.2)
1:(69.1, 45.6)
2:(93.6, 87.9)
3:(49.3, 94.0)
4:(12.5, 86.2)
5:(57.9, 71.8)
6:(68.2, 18.9)
7:(53.9, 78.8)
8:(65.9, 74.7)
9:(77.5, 84.4)
10:(15.3, 34.1)
(0)(4)(3)(7)(5)(8)(9)(2)(1)(6)(10)
min = 284.85
 time: 2 sec