ponder1810

ponder1810.c

/* gcc -W -Wall -O3 -o p p.c */
#include <stdio.h>
#include <stdlib.h>

#define N	11
#define LX	33
#define LY	16
#define TN	165

#define LX1	(LX + 1)
#define LY1	(LY + 1)
#define AMAX	(LX1 * LY1 * 3)

#define N1	6
#define TRY	1
#define ZONE	4

static int	x[N];
static int	y[N];
static int	ta[TN];
static char	tm[AMAX];
static int	lim;

static void
found (void) {
	int		i;

	printf ("!!!");
	for (i = 0; i < N; i++)
		printf (" %d,%d", x[i], y[i]);
	printf ("\n");
	exit (0);
}

static void
report (int tn, int d) {
	int		i;

	printf ("%d\t%d:", tn, d);
	for (i = 0; i < d; i++)
		printf (" %d,%d", x[i], y[i]);
	printf ("\n");
	fflush (stdout);
}

static void
rec (int d, int t, int xs, int ys);

static void
rec2 (int d, int t) {
	int		x1, y1, x2, y2, x3, y3, i1, i2, a, tn;

	tn = t;
	x3 = x[d]; y3 = y[d];
	for (i1 = 0; i1 < d - 1; i1++)
	for (i2 = i1 + 1; i2 < d; i2++) {
		x1 = x[i1]; y1 = y[i1];
		x2 = x[i2]; y2 = y[i2];
#if 0
		a = abs (x1*(y2-y3)+x2*(y3-y1)+x3*(y1-y2));
#else
		a = abs ((x1-x3)*(y2-y1)-(x1-x2)*(y3-y1));
#endif
		if (!a || tm[a]) {
			if (d == N - 1 && tn > lim && tn >= 142) {
				report (tn, d);
				lim = tn;
			}
			goto NEXT;
		}
		tm[a] = 1;
		ta[tn++] = a;
	}
	if (d >= N1) {
		rec (d + 1, tn, x3, y3);
	} else {
		lim = 0;
		rec (d + 1, tn, -1, 0);
	}
NEXT:	while (tn > t)
		tm[ta[--tn]] = 0;
}

static void
rec (int d, int t, int xs, int ys) {
	int		i, x3, y3;

	if (d == N)
		found ();
	if (d < N1 - 1) {
		for (i = 0; i < TRY; i++) {
			x[d] = d == 0 ? rand () % (LX1 / 2) :
				d == 2 ? 0 : d == 3 ? LX : rand () % LX1;
			y[d] =	d == 0 ? 0 : d == 1 ? LY : rand () % LY1;
			rec2 (d, t);
		}
	} else if (d == N1 - 1) {
		for (i = 0; i < TRY; i++) {
			y[d] = rand () % LY1;
			for (x3 = 0; x3 < LX1; x3++) {
				x[d] = x3;
				rec2 (d, t);
			}
		}
	} else {
		for (y3 = ys; y3 < LY1; y3++)
		for (x3 = y3 == ys ? xs + 1 : 0; x3 < LX1; x3++) {
#ifdef ZONE
			if (x3 >= ZONE && x3 < LX1 - ZONE &&
			    y3 >= ZONE && y3 < LY1 - ZONE)
				continue;
#endif
			x[d] = x3;
			y[d] = y3;
			rec2 (d, t);
		}
	}
}

int
main (void) {
	srand (3);
	for (;;)
		rec (0, 0, -1, 0);
	return 0;
}