/*	POTM ENTRY:	JigSaw			*/
/*	Your Name:	Andrew Gauld		*/
/*	Your email:	andrew.gauld@att.com	*/


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


struct strategy	{
	char	*pat;
	int	mask;
	int	code;
	int	minskip;
	int	maxskip;
};


struct strategy	Cuts[200] = {
	"3447c 66184 97e8c c9b94 13a748c 274e8b4 3af5cdc 4e9d104", 7, 0, 0, 9,
	"10b4921 21691de 321db00 42d2422 528b4a7 2a515 522b6 7c830 a6daa d1323", 4, 0, 0, 11,
	"31d6d 63a75 9577d c7485 ebd71f 1d7ae3d 2b3cc59 38fea75 46c0891 54826ad", 3, 0, 0, 11,
};


char	*Bestcut;
int	Bestcode;
int	Bestskip;
double	Bestscore;

int	Novert;

# ifndef DEBUG
# define PRINTF	dummy
# else
# define PRINTF printf
# endif


int
dummy(char *fmt, ...)
{
}

char	Swapcode[] = "0123456710325476230167453210765446570213574613026475203175643120";

# define SWAPCODE(first, second) (Swapcode[((first) << 3) + (second)] & 7)


void
putstrat(char *strat, int mask, int code, int minskip, int maxskip)
{
	int	i;

	for (i = 0; i < 199; i++) {
		if (Cuts[i].pat == NULL) {
			Cuts[i].pat = malloc(strlen(strat) + 1);
			strcpy(Cuts[i].pat, strat);
			Cuts[i].mask = mask;
			Cuts[i].code = code;
			Cuts[i].minskip = minskip;
			Cuts[i].maxskip = maxskip;
			break;
		}
	}
}


double	Xint;
double	Yint;
double	Area;
int	Orient;

struct jig	{	/* a line or a point */
	int	a;
	int	b;
	int	c;
};


struct xtract	{
	int	x0;
	int	y0;
	int	x1;
	int	y1;
};


void	xtoj(struct jig *j, struct xtract *x);


struct polygon	{
	int	edges[16];
	int	nedges;
};


struct solution	{
	struct jig lines[15];
	struct jig intercepts[15][15];
	struct polygon polygons[67];
	int	nlines;
	int	npolys;
	char	*desc;
	int	code;
};

int	ieval(struct solution *s);

# define XMIRROR	1
# define YMIRROR	2
# define XYSWAP		4
# define TRYS		8


struct polygon	Ipoly = { { 0, 1, 2, 3, 0 }, 4 };
struct jig	Initial[5] = {
	0, 1, 0, 1, 0, 100, 0, 1, 100, 1, 0, 0, 0, 0, 0
};


struct inter	{
	double	xint;
	double	yint;
};


void
jtointer(struct inter *i, struct jig *j)
{
	double	a;
	double	b;
	double	c;
	double	q;
	int	skip;

	a = j->a;
	b = j->b;
	c = j->c;
	skip = 0;
	if (a && (q = c / a) >= 0.0 && q < 100.0) {
		skip++;
		i->xint = q;
		skip++;
	}
	if (b && (q = (c - 100 * a) / b) >= 0.0 && q < 100.0) {
		if (skip++) {
			i->yint = 300.0 - q;
		} else {
			i->xint = q + 100.0;
		}
	}
	if (a && (q = (c - 100 * b) / a) > 0.0 && q <= 100.0) {
		if (skip++) {
			i->yint = q + 100.0;
		} else {
			i->xint = 300.0 - q;
		}
	}
	if (b && (q = c / b) > 0.0 && q <= 100.0) {
		i->yint = q;
	}
}


double
inttoa(struct inter *i)
{
	if (i->yint <= 100.0) {
		return(i->xint * i->yint / 2.0);
	}
	if (i->xint <= 100.0) {
		return(50 * (i->xint + i->yint - 100.0));
	}
	return(100.0 * (i->xint + i->yint) - 10000.0 - i->xint * i->yint / 2.0);
}


void
inttox(struct xtract *x, struct inter *i)
{
	x->x0 = 100;
	x->y0 = 0;
	x->x1 = 0;
	x->y1 = 100;
	if (i->xint > 100.0) {
		x->y0 = i->xint - 100.0;
	} else {
		x->x0 = i->xint;
	}
	if (i->yint > 100.0) {
		x->x1 = i->yint - 100.0;
	} else {
		x->y1 = i->yint;
	}
}


void
jiggle(struct xtract *xt, struct inter *it, int dir)
{
	struct xtract	xa;
	struct xtract	xb;
	struct inter	ia;
	struct inter	ib;
	struct jig	ja;
	struct jig	jb;

	ia = *it;
	ib = *it;
	ia.xint += dir;
	ib.yint += dir;
	if (ia.yint >= 200.0 || ia.yint <= ia.xint || ia.xint <= 0.0 || ia.yint >= ia.xint + 100.0) {
		ia = ib;
	} else if (ib.yint >= 200 || ib.yint <= ib.xint || ib.xint <= 0.0 || ib.yint >= ib.xint + 100.0) {
		;
	} else {
		inttox(&xa, &ia);
		inttox(&xb, &ib);
		if (gcd(xa.x1 - xa.x0, xa.y1 - xa.y0) > gcd(xb.x1 - xb.x0, xb.y1 - xb.y0)) {
			ia = ib;
		}
	}
	PRINTF("Jiggle %g %g to %g %g (%d)\n", it->xint, it->yint, ia.xint, ia.yint, dir);
	*it = ia;
	inttox(xt, it);
}


# define MIN(i, j)	(((i) < (j))? (i): (j))
# define MAX(i, j)	(((i) > (j))? (i): (j))


void
tweak(struct xtract *xt, double want)
{
	struct xtract	x1;
	struct xtract	x2;
	struct xtract	x3;
	struct xtract	bx;
	double	berr;
	struct inter	itr;
	struct jig	jg;
	double	s1;
	double	s2;
	double	ws;
	double	got1;
	double	got2;
	int	i;
	int	j;
	int	k;

	xtoj(&jg, xt);
	jtointer(&itr, &jg);
	got1 = inttoa(&itr);
	berr = fabs(got1 - want);
	bx = *xt;
	if (berr < 1.0) {
		return;
	}
	jiggle(&x1, &itr, 1);
	got1 = inttoa(&itr);
	got2 = got1;
	x2 = x1;
	if (got1 > want) {
		do {
			x2 = x1;
			got2 = got1;
			jiggle(&x1, &itr, -1);
			got1 = inttoa(&itr);
		} while (got1 > want);
	} else {
		do {
			x1 = x2;
			got1 = got2;
			jiggle(&x2, &itr, 1);
			got2 = inttoa(&itr);
		} while (got2 < want);
	}
	s1 = (x1.x1 - x1.x0) / (double)(x1.y0 - x1.y1);
	s2 = (x2.x1 - x2.x0) / (double)(x2.y0 - x2.y1);
	ws = s1 + (s2 - s1) * (want - got1) / (got2 - got1);
	x3 = x1;
	PRINTF("got1 = %g got2 = %g\n", got1, got2);
	i = MIN(x1.x1, x2.x1);
	j = MAX(x1.x0, x2.x0);
	if (fabs(got1 - want) < berr) {
		PRINTF("x1 closer\n");
		berr = fabs(got1 - want);
		bx = x1;
	}
	if (fabs(got2 - want) < berr) {
		PRINTF("x2 closer\n");
		berr = fabs(got2 - want);
		bx = x2;
	}
	if (x1.x0 == x2.x0 && x1.y0 == x2.y0) {
		/* adjust x1/y1 end */
		PRINTF("TWEAK x1/y1 %d %d %g %g %g\n", i, j, s1, s2, ws);
		for (i++; i < j; i++) {
			k = x1.y0 + 0.5 + (x1.x0 - i) / ws;
			PRINTF("x %d y %d\n", i, k);
			if (k < 0 || k > 100) {
				continue;
			}
			x3.x1 = i;
			x3.y1 = k;
			xtoj(&jg, &x3);
			jtointer(&itr, &jg);
			got1 = inttoa(&itr);
			got2 = fabs(got1 - want);
			if (got2 < berr) {
				berr = got2;
				bx = x3;
			}
		}
	} else {
		/* adjust x0/y0 end */
		PRINTF("TWEAK x0/y0 %d %d %g %g %g\n", i, j, s1, s2, ws);
		for (i++; i < j; i++) {
			k = x1.y1 + 0.5 + (x1.x1 - i) / ws;
			if (k < 0 || k > 100) {
				continue;
			}
			x3.x0 = i;
			x3.y0 = k;
			xtoj(&jg, &x3);
			jtointer(&itr, &jg);
			got1 = inttoa(&itr);
			got2 = fabs(got1 - want);
			if (got2 < berr) {
				berr = got2;
				bx = x3;
			}
		}
	}
	*xt = bx;
}


double
slice(struct xtract *xt, struct inter *o, struct inter *i, double want)
{
	int	b;
	double	c;
	int	x;
	struct jig	j;

	b = i->yint - i->xint;
	if (want <= 5000.0) {
		x = (-b + sqrt(b * b + 8.0 * want)) / 2.0;
		x += 0.5;
		if (x + b <= 100.0) {
			o->xint = x;
			o->yint = x + b;
			inttox(xt, o);
			tweak(xt, want);
			xtoj(&j, xt);
			jtointer(o, &j);
			return(inttoa(o));
		}
	} else {
		x = 200 - (b + sqrt(b * b + 8.0 * (10000.0 - want))) / 2.0;
		x += 0.5;
		if (x >= 100.0) {
			o->xint = x;
			o->yint = x + b;
			inttox(xt, o);
			tweak(xt, want);
			xtoj(&j, xt);
			jtointer(o, &j);
			return(inttoa(o));
		}
	}
	x = (want + 5050 - 50 * b) / 100.0;
	o->xint = x;
	o->yint = x + b;
	inttox(xt, o);
	tweak(xt, want);
	xtoj(&j, xt);
	jtointer(o, &j);
	return(inttoa(o));
}


char *
putx(char *buf, struct xtract *x)
{
	sprintf(buf, "%x ", ((x->x0 * 101 + x->y0) * 101 + x->x1) * 101 + x->y1);
	return(buf + strlen(buf));
}


int
inttry(char *buf, int m, int n, double ba, struct inter *i)
{
	double	qa;
	double	pa;
	double	da;
	int	j;
	int	min;
	int	max;
	int	cur;
	struct inter	ni;
	struct inter	oi;
	struct xtract	x;

	min = 10000;
	max = 0;
	pa = ba;
	oi = *i;
	for (j = m - 1; j > 0; j--) {
		da = (pa * j) / (j + 1);
		qa = slice(&x, &ni, &oi, da);
		buf = putx(buf, &x);
		cur = pa - qa;
		pa = qa;
		oi = ni;
		if (cur > max) {
			max = cur;
		}
		if (cur < min) {
			min = cur;
		}
	}
	cur = pa;
	if (cur > max) {
		max = cur;
	}
	if (cur < min) {
		min = cur;
	}
	pa = ba;
	oi = *i;
	for (j = m + 1; j < n; j++) {
		da = 10000.0 - ((10000.0 - pa) * (n - j)) / (n - j + 1);
		qa = slice(&x, &ni, &oi, da);
		buf = putx(buf, &x);
		cur = qa - pa;
		pa = qa;
		oi = ni;
		if (cur > max) {
			max = cur;
		}
		if (cur < min) {
			min = cur;
		}
	}
	cur = 10000.0 - pa;
	if (cur > max) {
		max = cur;
	}
	if (cur < min) {
		min = cur;
	}
	buf[-1] = '\0';
	return(max - min);
}


void
slicer()
{
	char	buf[BUFSIZ];
	char	bestbuf[BUFSIZ];
	int	best;
	int	cur;
	int	m;
	int	n;
	double	ba;
	struct inter	i;
	int	p;

	if (Yint <= 100.0) {
		if (Xint * Yint < 1200.0) {
			return;
		}
	} else {
		if (50 * (Xint + Yint) < 5600) {
			return;
		}
	}
	cur = 10000;
	i.xint = Xint;
	i.yint = Yint;
	best = 10000;
	ba = inttoa(&i);
	for (n = 3; n <= 12; n++) {
		p = n * ba / 10000.0;
		for (m = p - 1; m <= p + 2; m++) {
			if (m < 1 || m >= n) {
				continue;
			}
			cur = inttry(buf, m, n, ba, &i);
			PRINTF("%d %d %s scores %d\n", m, n, buf, cur);
			if (cur < best) {
				strcpy(bestbuf, buf);
				best = cur;
			}
		}
	}
	if (best < 300) {
		putstrat(bestbuf, 7, Orient, 10, 11);
	}
}


double
polyarea(struct solution *s, struct polygon *p)
{
	int	i;
	double	d;
	double	x0;
	double	x1;
	double	y0;
	double	y1;
	struct jig	*j;

	p->edges[p->nedges] = p->edges[0];
	j = &(s->intercepts[p->edges[p->nedges - 1]][p->edges[0]]);
	x0 = j->a / (double)(j->c);
	y0 = j->b / (double)(j->c);
	d = 0.0;
	PRINTF("Computing area:");
	for (i = 0; i < p->nedges; i++) {
		j = &(s->intercepts[p->edges[i]][p->edges[i + 1]]);
		x1 = j->a / (double)(j->c);
		y1 = j->b / (double)(j->c);
		d += (y0 + y1) * (x0 - x1) / 2.0;
		PRINTF("(%g, %g) - (%g, %g) => %g\n", x0, y0, x1, y1, d);
		x0 = x1;
		y0 = y1;
	}
	if (d < 0) {
		d = -d;
	}
	return(d);
}


char	*
dget(char *desc, int code, struct xtract *x)
{
	int	i;

	while (isspace(*desc)) {
		desc++;
	}
	if (!*desc) {
		return(NULL);
	}
	i = strtol(desc, &desc, 16);
	if (i == 0) {
		return(NULL);
	}
	x->y1 = i % 101;
	i /= 101;
	x->x1 = i % 101;
	i /= 101;
	x->y0 = i % 101;
	x->x0 = i / 101;
	if (code & XMIRROR) {
		x->x0 = 100 - x->x0;
		x->x1 = 100 - x->x1;
	}
	if (code & YMIRROR) {
		x->y0 = 100 - x->y0;
		x->y1 = 100 - x->y1;
	}
	if (code & XYSWAP) {
		i = x->x0;
		x->x0 = x->y0;
		x->y0 = i;
		i = x->x1;
		x->x1 = x->y1;
		x->y1 = i;
	}
	return(desc);
}


void
report(char *desc, int code, int skip)
{
	struct xtract	x;
	int	a;
	int	b;
	int	c;
	int	i;
	int	j;

	a = Initial[4].a;
	b = Initial[4].b;
	c = Initial[4].c;
	i = -1;
	j = 0;
	while (desc = dget(desc, code, &x)) {
		i++;
		if (x.x0 * a + x.y0 * b == c &&
		    x.x1 * a + x.y1 * b == c) {
			continue;
		}
		if (i == skip) {
			continue;
		}
		j++;
		if (j > 10) {
			break;
		}
		printf("%d %d %d %d\n", x.x0, x.y0, x.x1, x.y1);
	}
}


int
gcd(int a, int b)
{
	if (a < 0) {
		a = -a;
	}
	if (b < 0) {
		b = -b;
	}
	if (a == 0 || b == 0) {
		return(a + b);
	}
	if (a == 1 || b == 1) {
		return(1);
	}
	while (a != 0) {
		b %= a;
		if (b == 0) {
			return(a);
		}
		a %= b;
	}
	return(b);
}


void
jreduce(struct jig *j)
{
	int	rat;

	rat = gcd(j->a, j->b);
	rat = gcd(rat, j->c);
	if (rat > 1) {
		j->a /= rat;
		j->b /= rat;
		j->c /= rat;
	}
	if (j->c < 0) {
		j->a = -(j->a);
		j->b = -(j->b);
		j->c = -(j->c);
	}
}


void
xtoj(struct jig *j, struct xtract *x)
{
	j->a = x->y1 - x->y0;
	j->b = x->x0 - x->x1;
	j->c = x->x0 * j->a + x->y0 * j->b;
	jreduce(j);
}


void
intercept(struct jig *p, struct jig *a, struct jig *b)
{
	p->c = b->b * a->a - b->a * a->b;
	p->a = b->b * a->c - b->c * a->b;
	p->b = b->c * a->a - b->a * a->c;
	jreduce(p);
}


int
eval(struct solution *s, char *cut, int code, int skip)
{
	int	i;
	double	sc;
	struct xtract	x;
	char	*ocut;

	s->nlines = 5;
	i = 0;
	ocut = cut;
	while (s->nlines < 15 && (cut = dget(cut, code, &x))) {
		if (i++ == skip) {
			continue;
		}
		xtoj(&(s->lines[s->nlines++]), &x);
	}
	sc = ieval(s);
	PRINTF("%s %d %d scores %d\n", ocut, code, skip, (int)sc);
	if (sc < Bestscore) {
		PRINTF("NEW BEST\n");
		Bestcut = ocut;
		Bestcode = code;
		Bestskip = skip;
		Bestscore = sc;
	}
	return((int)sc);
}


int
ieval(struct solution *s)
{
	int	i;
	int	j;
	int	k;
	double	a;
	double	min;
	double	max;
	struct jig	ji;

	if (s->nlines <= 5) {
		return(10000);
	}
	s->lines[0] = Initial[0];
	s->lines[1] = Initial[1];
	s->lines[2] = Initial[2];
	s->lines[3] = Initial[3];
	s->lines[4] = Initial[4];
	s->npolys = 1;
	s->polygons[0] = Ipoly;
	for (i = 0; i < s->nlines; i++) {
		for (j = 0; j < s->nlines; j++) {
			intercept(&(s->intercepts[i][j]), &(s->lines[i]), &(s->lines[j]));
			PRINTF("[%d][%d] %dx + %dy = %d, %dx + %dy = %d => (%g, %g)\n", i, j, s->lines[i].a, s->lines[i].b, s->lines[i].c,
			    s->lines[j].a, s->lines[j].b, s->lines[j].c,
			    s->intercepts[i][j].a / (double)(s->intercepts[i][j].c),
			    s->intercepts[i][j].b / (double)(s->intercepts[i][j].c));
		}
	}
	for (i = 4; i < s->nlines; i++) {
		k = s->npolys;
		for (j = 0; j < k; j++) {
			s->npolys += polycut(s, &(s->polygons[j]), &(s->polygons[s->npolys]), i);
		}
	}
	min = 10000;
	max = 0;
	for (k = 0; k < s->npolys; k++) {
		a = polyarea(s, &(s->polygons[k]));
		if (a < min) {
			min = a;
		}
		if (a > max) {
			max = a;
		}
	}
	j = max - min;
	return(j);
}


int
polycut(struct solution *s, struct polygon *p1, struct polygon *p2, int edge)
{
	int	e1;
	int	e2;
	int	i;
	int	j;
	int	k;
	int	x[15];
	struct jig	*p;
	struct jig	*q;
	struct jig	*xx;

	e1 = -1;
	e2 = -1;
	p1->edges[p1->nedges] = p1->edges[0];
	p = &(s->intercepts[p1->edges[0]][p1->edges[p1->nedges - 1]]);
	for (i = 0; i < p1->nedges; i++, p = q) {
		q = &(s->intercepts[p1->edges[i]][p1->edges[i + 1]]);
		xx = &(s->intercepts[edge][p1->edges[i]]);
		if (xx->c && xx->a == q->a && xx->b == q->b && xx->c == q->c) {
			if (e1 == -1) {
				e1 = i + i + 1;
			} else {
				e2 = i + i + 1;
			}
			continue;
		}
		if (xx->a == p->a && xx->b == p->b && xx->c == p->c) {
			continue;
		}
		if (xx->c == 0) {
			continue;
		}
		/* watch out for really big numbers (up to 20 billion) */
		if ((p->a * (double)(xx->c) - xx->a * (double)(p->c)) *
		    (q->a * (double)(xx->c) - xx->a * (double)(q->c)) > 0.0) {
			continue;
		}
		if ((p->b * (double)(xx->c) - xx->b * (double)(p->c)) *
		    (q->b * (double)(xx->c) - xx->b * (double)(q->c)) > 0.0) {
			continue;
		}
		if (e1 == -1) {
			e1 = i + i;
		} else {
			e2 = i + i;
		}
	}
	if (e2 == -1) {
		return(0);
	}
	p2->nedges = 1;
	p2->edges[0] = edge;
	j = e2 / 2;
	for (i = (e1 + 1) / 2; i <= j; i++) {
		p2->edges[p2->nedges++] = p1->edges[i];
	}
	i = e1 / 2 + 1;
	j = (e2 + 1) / 2;
	for (k = 0; k < i; k++) {
		x[k] = p1->edges[k];
	}
	x[k++] = edge;
	for ( ; j < p1->nedges; j++) {
		x[k++] = p1->edges[j];
	}
	p1->nedges = k;
	for (i = 0; i < k; i++) {
		p1->edges[i] = x[i];
	}
	return(1);
}


struct dvect	{
	double	x0;
	double	y0;
	double	x1;
	double	y1;
};


void
itodv(struct dvect *dv, double xint, double yint)
{
	dv->x0 = 100.0;
	dv->y0 = 0.0;
	dv->x1 = 0.0;
	dv->y1 = 100.0;
	if (xint <= 100.0) {
		dv->x0 = xint;
	} else {
		dv->y0 = xint - 100.0;
	}
	if (yint <= 100.0) {
		dv->y1 = yint;
	} else {
		dv->x1 = yint - 100.0;
	}
}


char *
nlt(char *buf, double xint, double yint)
{
	struct dvect	dv;
	struct inter	in;
	struct xtract	bx;
	struct xtract	x;
	struct jig	jg;
	double	bd;
	double	d;
	double	a;
	double	b;
	double	c;
	int	i;
	int	j;
	int	k;

	in.xint = xint + 0.5;
	in.yint = yint + 0.5;
	inttox(&bx, &in);
	bd = fabs(in.xint - xint) + fabs(in.yint - yint);
	if (fabs(fabs(xint - yint) - 100.0) < 0.5) {
		return(putx(buf, &bx));
	}
	itodv(&dv, xint, yint);
	a = dv.y1 - dv.y0;
	b = dv.x0 - dv.x1;
	c = dv.x0 * a + dv.y0 * b;
	k = ceil(MAX(dv.x0, dv.x1));
	for (x.x0 = floor(MIN(dv.x0, dv.x1)); x.x0 < k; x.x0++) {
		for (x.x1 = x.x0 + 1; x.x1 <= k; x.x1++) {
			x.y0 = (c - x.x0 * a) / b;
			x.y1 = (c - x.x1 * a) / b;
			if (x.y0 < 0) {
				x.y0 = 0;
			}
			if (x.y0 > 99) {
				x.y0 = 99;
			}
			if (x.y1 < 0) {
				x.y1 = 0;
			}
			if (x.y1 > 99) {
				x.y1 = 99;
			}
# define XBST()	xtoj(&jg, &x); jtointer(&in, &jg); d = fabs(in.xint - xint) + fabs(in.yint - yint); if (d < bd) { bd = d; bx = x; }
			XBST();
			x.y0++;
			XBST();
			x.y1++;
			XBST();
			x.y0--;
			XBST();
		}
	}
	return(putx(buf, &bx));
}


char *
xslash(char *buf, double a, double b, double c, double A)
{
	double	x;
	double	y;
	double	aa;
	double	bb;
	double	cc;
	int	flip;

	flip = 0;
	if (A > 5000.0) {
		flip = 1;
		A = 10000 - A;
	}
	aa = b;
	bb = -4 * c;
	cc = 2 * (c * c / b + a * A);
	y = (-bb + sqrt(bb * bb - 4 * aa * cc)) / 2 / aa;
	if (y <= 100) {
		x = 2 * A / y;
	} else {
		if (a != 0) {
			aa = -5000 * a * b;
			bb = -10000 * b * c + 100 * a * b * A + 100 * c * c;
			cc = 200 * b * c * A - 5000 * A * b * b - a * b * A * A - A * c * c;
			y = (-bb - sqrt(bb * bb - 4 * aa * cc)) / 2 / aa + 100;
		} else {
			y = A / 100 + 100;
		}
		x = A / 50 - y + 100;
	}
	if (flip) {
		a = x;
		x = 200 - y;
		y = 200 - a;
	}
	return(nlt(buf, x, y));
}


void
xslice2(int m, int n)
{
	double	a;
	double	b;
	double	c;
	double	aa;
	double	bb;
	double	cc;
	int	i;
	char	buf[BUFSIZ];
	char	*cp;

	if (m <= 0 || n <= 0) {
		return;
	}
	if (fabs(Area / m - (10000 - Area) / n) / 2 > 288) {
		return;
	}
	if (Yint <= 100.0) {
		bb = (Xint - 200) * Yint + 10000;
		cc = (50 * Yint * Yint - 10000 * Yint + 250000);
		a = (-bb - sqrt(bb * bb - 400 * cc)) / 200;
		b = 50;
	} else {
		if (Xint == Yint - 100) {
			a = 0;
		} else {
			aa = Yint - 100 - Xint;
			bb = 100 * (Xint + Yint - 100) - Xint * Xint - (Yint - 100) * (Yint - 100);
			cc = 2500 * (Xint - Yint + 100);
			a = (-bb + sqrt(bb * bb - 4 * aa * cc)) / 2 / aa;
		}
		b = 50;
	}
	c = (a + b) * 50;
	if (b < 0) {
		a = -a;
		b = -b;
		c = -c;
	}
	cp = nlt(buf, 200 - c / b, c / b);
	for (i = 1; i < m; i++) {
		cp = xslash(cp, a, b, c, (Area * (double)i) / (double)m);
	}
	for (i = 1; i < n; i++) {
		cp = xslash(cp, a, b, c, 10000.0 - ((10000.0 - Area) * (double)i) / (double)n);
	}
	putstrat(buf, 7, Orient, 10, 11);
}


void
tryslice2()
{
	int	i;
	int	j;

	for (i = 2; i <= 11; i++) {
		j = i * Area / 10000.0;
		xslice2(j, i - j);
		xslice2(j + 1, i - j - 1);
	}
}


void
try3x4()
{
	char	buf[BUFSIZ];
	int	z;

	if (Yint * Xint < 181.0) {
		return;
	}
	if (Xint > 25.0) {
		return;
	}
	if (Yint > 32.0) {
		return;
	}
	z = (Xint * Yint + 25.0) / 125.0 + 10.0;
	while (z + z < Yint) {
		z++;
	}
	sprintf(buf, "1891133 3122265 49b3397 %x %x %x %x %x %x %x", 0x1890787 + 0x4fb3 * z, 0x190d01b + 0x27d9 * z, 0x319e14d + 0x27d9 * z, 0x4a2f27f + 0x27d9 * z, 0x62c03b1 + 0x27d9 * z, 0x65 + 0x4fb4 * z, 0x7c8f9 + 0x27da * z);
	putstrat(buf, 7, Orient, 10, 11);
	PRINTF("try3x4 z=%d\n", z);
}


double
vdist(struct xtract *x, struct dvect *got, struct dvect *want)
{
	int	a;
	int	b;
	int	c;

	if (x->x0 < 0 || x->x0 > 100 || x->x1 < 0 || x->x1 > 100 ||
	    x->y0 < 0 || x->y0 > 100 || x->y1 < 0 || x->y1 > 100 || x->y0 == x->y1) {
		*got = *want;
		return(200.0);
	}
	a = x->y1 - x->y0;
	b = x->x0 - x->x1;
	c = a * x->x0 + b * x->y0;
	got->y0 = want->y0;
	got->y1 = want->y1;
	got->x0 = (c - b * want->y0) / a;
	got->x1 = (c - b * want->y1) / a;
	return(fabs(got->x0 - want->x0) + fabs(got->x1 - want->x1));
}


# define BST() if ((d = vdist(&x, &v, w)) < bd) { bd = d; bx = x; bv = v; }
			

void
bvect(struct xtract *z, struct dvect *w)
{
	int	i;
	int	j;
	int	k;
	int	l;
	double	a;
	double	b;
	double	c;
	double	bd;
	struct dvect	bv;
	struct xtract	bx;
	double	d;
	struct dvect	v;
	struct xtract	x;
	struct dvect	tw;

	bx.y0 = 1;
	bx.y1 = 0;
	if (Novert) {
		bx.x0 = 0;
		bx.x1 = 1;
		bd = vdist(&bx, &bv, w);
	} else {
		bx.x0 = (w->x0 + w->x1 + 1.0) / 2.0;
		bx.x1 = bx.x0;
		bv = *w;
		bv.x0 = bx.x0;
		bv.x1 = bx.x1;
		bd = fabs(bv.x0 - w->x0) + fabs(bv.x1 - w->x1);
	}
	a = w->y1 - w->y0;
	b = w->x0 - w->x1;
	c = w->x0 * a + w->y0 * b;
	d = c / a;
	if (d < Xint) {
		tw = *w;
		tw.x1 = Xint + .01;
		tw.y1 = 0.0;
		w = &tw;
		a = w->y1 - w->y0;
		b = w->x0 - w->x1;
		c = w->x0 * a + w->y0 * b;
		d = c / a;
	}
	i = (c - b * 100.0) / a;
	j = ceil(d);
	for (x.x0 = i; x.x0 < j; x.x0++) {
		for (x.x1 = x.x0 + 1; x.x1 <= j; x.x1++) {
			x.y0 = (c - a * x.x0) / b;
			x.y1 = (c - a * x.x1) / b;
			if (x.y0 < 0) x.y0 = 0;
			if (x.y0 > 100) x.y0 = 100;
			if (x.y1 < 0) x.y1 = 0;
			if (x.y1 > 100) x.y1 = 100;
			BST();
			x.y1++;
			BST();
			x.y0++;
			BST();
			x.y1--;
			BST();
		}
	}
	*w = bv;
	*z = bx;
}


void
trydnplus(int n)
{
	struct xtract	x;
	struct dvect	d;
	int		z;
	double		q;
	int		i;
	int		j;
	int		k;
	char		buf[BUFSIZ];
	char		*cp;
	double		a;

	if (Yint > 66.0 || Xint > 50.0) {
		return;
	}
	a = Xint * Yint / 2.0;
	if (fabs((10000.0 - a) / (n + n + 1) - a) > 288.0) {
		return;
	}
	z = 100.0 - n * (10000 - a) / (n + n + 1) / 100.0;
	if (z < Yint) {
		z = ceil(Yint);
	}
	sprintf(buf, "%x", 0x65 + z * 0x27da);
	cp = buf + strlen(buf);
	d.x1 = a / z + 100.0 / (n + 1);
	q = d.x1 * 2;
	d.y1 = z / 2.0;
	d.x0 = 0;
	d.y0 = 50 + d.y1;
	d.x0 = d.x0 + (100.0 - d.x0) / n;
	d.x1 = d.x1 + (100.0 - d.x1) / n;
	j = ceil(q);
	if (j < Xint) {
		j = ceil(Xint);
	}
	bvect(&x, &d);
	if (d.x0 + 1.5 * (d.x1 - d.x0) < j) {
		x.x1 = j;
		x.y1 = 0;
	}
	k = (q * z) / j;
	if (k < Yint) {
		k = ceil(Yint);
	}
	sprintf(cp, " %x ", 0x27d9 * k + 0x65 * j);
	cp += strlen(cp);
	cp = putx(cp, &x);
	for (i = 2; i < n; i++) {
		d.x0 = d.x0 + (100.0 - d.x0) / (n - i + 1);
		d.x1 = d.x1 + (100.0 - d.x1) / (n - i + 1);
		bvect(&x, &d);
		cp = putx(cp, &x);
	}
	putstrat(buf, 7, Orient, 10, 11);
}


void
tryodd(int n)
{
	struct xtract	x;
	struct dvect	d;
	int		z;
	double		q;
	int		i;
	char		buf[BUFSIZ];
	char		*cp;

	Novert = 1;
	if (Yint > 66.0) {
		return;
	}
	z = 50.5 + (Xint * Yint) / 400.0;
	if (z < Yint) {
		z = ceil(Yint);
	}
	if (fabs(Xint * Yint / 2.0 - (100.0 * z - Xint * Yint / 2.0) / n) > 288.0) {
		return;
	}
	sprintf(buf, "%x ", 0x65 + z * 0x27da);
	cp = buf + strlen(buf);
	d.x1 = Xint * Yint / z / 2.0;
	d.y1 = z / 2.0;
	d.x0 = 0;
	d.y0 = 50 + d.y1;
	for (i = 1; i < n; i++) {
		d.x0 = d.x0 + (100.0 - d.x0) / (n - i + 1);
		d.x1 = d.x1 + (100.0 - d.x1) / (n - i + 1);
		bvect(&x, &d);
		cp = putx(cp, &x);
	}
	putstrat(buf, 7, Orient, 10, 11);
	Novert = 0;
}


double	areas[11][11];
double	horiz[11][2];
double	vert[11][2];
double	Delta;
double	Score;
double	mn;
double	mx;


init(int m, int n)
{
	int	i;

	for (i = 0; i < m - 1; i++) {
		horiz[i][1] = (i + 1) * 100.0 / m;
		horiz[i][0] = horiz[i][1] + 100.0;
	}
	horiz[i][0] = 200.0;
	horiz[i][1] = 100.0;
	for (i = 0; i < n - 1; i++) {
		vert[i][0] = (i + 1) * 100.0 / n;
		vert[i][1] = vert[i][0] + 100.0;
	}
	vert[i][0] = 100.0;
	vert[i][1] = 200.0;
}


double
rarea(int h, int v)
{
	double	yint;
	double	xint;
	double	x1;
	double	y1;
	double	dy;
	double	dx;
	double	det;

	if (h < 0 || v < 0) {
		return(0.0);
	}
	yint = horiz[h][1];
	xint = vert[v][0];
	dy = yint + 100.0 - horiz[h][0];
	dx = xint + 100.0 - vert[v][1];
	det = dy * dx / 100.0 - 100.0;
	x1 = (yint * dx - 100.0 * xint) / det;
	y1 = (xint * dy - 100.0 * yint) / det;
	return(((yint + y1) * x1 + (xint - x1) * y1) / 2.0);
}


double
parea(int h, int v)
{
	return(rarea(h, v) + rarea(h - 1, v - 1) - rarea(h, v - 1) - rarea(h - 1, v));
}

double
score(int m, int n)
{
	int	i;
	int	j;

	for (i = 0; i < m; i++) {
		for (j = 0; j < n; j++) {
			areas[i][j] = parea(i, j);
		}
	}
	areas[0][0] -= Area;
	mn = Area;
	mx = Area;
	for (i = 0; i < m; i++) {
		for (j = 0; j < n; j++) {
			if (areas[i][j] > mx) {
				mx = areas[i][j];
			}
			if (areas[i][j] < mn) {
				mn = areas[i][j];
			}
		}
	}
	return(mx - mn);
}


void
diffadj(double *d1, double *d2)
{
	double	*dp;
	double	x;
	double	y;

	if (*d1 > *d2) {
		dp = d1;
		d1 = d2;
		d2 = dp;
	}
	if (ceil(*d1) >= floor(*d2)) {
		*d1 -= .02;
		*d2 += .02;
	}
}


void
adj(int m, int n)
{
	double	d0;
	double	d1;
	double	dt;
	double	e;
	int	i;
	int	j;

	for (i = 0; i < m - 1; i++) {
		dt = 0;
		d0 = 0;
		d1 = 0;
		for (j = 0; j < n; j++) {
			e = mn + Delta - areas[i][j];
			if (e > 0) {
				dt += n + n;
				d0 += (n + n - 1 - j - j) * e;
				d1 += (j + j + 1) * e;
			}
			e = areas[i][j] - mx + Delta;
			if (e > 0) {
				dt += n + n;
				d0 -= (n + n - 1 - j - j) * e;
				d1 -= (j + j + 1) * e;
			}
			e = mn + Delta - areas[i + 1][j];
			if (e > 0) {
				dt += n + n;
				d0 -= (n + n - 1 - j - j) * e;
				d1 -= (j + j + 1) * e;
			}
			e = areas[i + 1][j] - mx + Delta;
			if (e > 0) {
				dt += n + n;
				d0 += (n + n - 1 - j - j) * e;
				d1 += (j + j + 1) * e;
			}
		}
		if (dt) {
			horiz[i][1] += n * d0 / dt / 100;
			horiz[i][0] += n * d1 / dt / 100;
		}
		horiz[i][0] -= 100;
		diffadj(&(horiz[i][0]), &(horiz[i][1]));
		horiz[i][0] += 100;
	}
	for (j = 0; j < n - 1; j++) {
		dt = 0;
		d0 = 0;
		d1 = 0;
		for (i = 0; i < m; i++) {
			e = mn + Delta - areas[i][j];
			if (e > 0) {
				dt += m + m;
				d0 += (m + m - 1 - i - i) * e;
				d1 += (i + i + 1) * e;
			}
			e = areas[i][j] - mx + Delta;
			if (e > 0) {
				dt += m + m;
				d0 -= (m + m - 1 - i - i) * e;
				d1 -= (i + i + 1) * e;
			}
			e = mn + Delta - areas[i][j + 1];
			if (e > 0) {
				dt += m + m;
				d0 -= (m + m - 1 - i - i) * e;
				d1 -= (i + i + 1) * e;
			}
			e = areas[i][j + 1] - mx + Delta;
			if (e > 0) {
				dt += m + m;
				d0 += (m + m - 1 - i - i) * e;
				d1 += (i + i + 1) * e;
			}
		}
		if (dt) {
			vert[j][0] += m * d0 / dt / 100;
			vert[j][1] += m * d1 / dt / 100;
		}
		vert[j][1] -= 100;
		diffadj(&(vert[j][0]), &(vert[j][1]));
		vert[j][1] += 100;
	}
	if (vert[0][0] < Xint) {
		vert[0][0] = Xint;
	}
	if (horiz[0][1] < Yint) {
		horiz[0][1] = Yint;
	}
}


void
anal(int m, int n)
{
	int	i;
	char	buf[BUFSIZ];
	char	*cp;

	if (Yint > 100) {
		return;
	}
	if (fabs((10000 - Area) / m / n - Area) > 288) {
		return;
	}
	init(m, n);
	for (i = 0; i < 100; i++) {
		Score = score(m, n);
		Delta = (mx - mn) / 4;
		adj(m, n);
	}
	for (i = 0; i < 100; i++) {
		Score = score(m, n);
		Delta = (mx - mn) / 10;
		adj(m, n);
	}
	for (i = 0; i < 100; i++) {
		Score = score(m, n);
		Delta = 1;
		adj(m, n);
	}
	cp = buf;
	for (i = 0; i < m - 1; i++) {
		cp = nlt(cp, horiz[i][0], horiz[i][1]);
	}
	for (i = 0; i < n - 1; i++) {
		cp = nlt(cp, vert[i][0], vert[i][1]);
	}
	putstrat(buf, 7, Orient, 10, 11);
}


int
main(int argc, char **argv)
{
	struct xtract	x;
	char	*cut;
	struct strategy	*cuts;
	int	code;
	int	skip;
	int	score;
	struct solution	s;
	struct inter	itr;
	double	q;

	Bestscore = 10000;
	Orient = 0;
	if (argc != 5) {
		return(1);
	}
	x.x0 = atoi(argv[1]);
	x.y0 = atoi(argv[2]);
	x.x1 = atoi(argv[3]);
	x.y1 = atoi(argv[4]);
	xtoj(&Initial[4], &x);
	jtointer(&itr, &Initial[4]);
	Xint = itr.xint;
	Yint = 400.0 - itr.yint;
	while (Xint >= 100.0 || Yint < 200.0 || (Yint == 200.0 && Xint != 0.0)) {
		Xint += 100.0;
		Yint += 100.0;
		if (Yint >= 400.0) {
			q = Xint;
			Xint = Yint - 400.0;
			Yint = q;
		}
		PRINTF("ROT\n");
		Orient = SWAPCODE(XYSWAP | XMIRROR, Orient);
	}
	Yint = 400.0 - Yint;
	if (Yint < Xint) {
		q = Xint;
		Xint = Yint;
		Yint = q;
		PRINTF("XYSWAP\n");
		Orient = SWAPCODE(XYSWAP, Orient);
	}
	if (Xint + Yint > 200.0) {
		Xint = 100.0 - Xint;
		Yint = 300.0 - Yint;
		Orient = SWAPCODE(XMIRROR, Orient);
		PRINTF("XMIRROR\n");
	}
	if (Yint > Xint + 100.0) {
		q = Yint - 100.0;
		Yint = Xint + 100.0;
		Xint = q;
		Orient = SWAPCODE(YMIRROR, Orient);
		PRINTF("YMIRROR\n");
	}
	PRINTF("Xint = %g, Yint = %g, Orient %d\n", Xint, Yint, Orient);
	itr.xint = Xint;
	itr.yint = Yint;
	Area = inttoa(&itr);
	tryodd(10);
	tryodd(9);
	tryodd(8);
	tryodd(7);
	tryodd(6);
	tryodd(5);
	tryodd(4);
	tryodd(3);
	trydnplus(9);
	trydnplus(8);
	trydnplus(7);
	trydnplus(6);
	trydnplus(5);
	try3x4();
	slicer();
	tryslice2();
	anal(2, 10);
	anal(2, 9);
	anal(2, 8);
	anal(2, 7);
	anal(2, 6);
	anal(2, 5);
	anal(3, 9);
	anal(3, 8);
	anal(3, 7);
	anal(3, 6);
	anal(3, 5);
	anal(3, 4);
	anal(4, 8);
	anal(4, 7);
	anal(4, 6);
	anal(4, 5);
	anal(4, 4);
	anal(5, 7);
	anal(5, 6);
	anal(5, 5);
	for (cuts = Cuts; cut = cuts->pat; cuts++) {
		for (code = 0; code < 8; code++) {
			if (code & cuts->mask) {
				continue;
			}
			for (skip = cuts->minskip; skip < cuts->maxskip; skip++) {
				score = eval(&s, cut, code ^ cuts->code , skip);
			}
		}
	}
	report(Bestcut, Bestcode, Bestskip);
	return(0);
}