+
+ /*
+ * Ensure we haven't rounded a good solution to a worse one, by
+ * finding the new minimum fragment and making sure it's at
+ * least the one we previously had.
+ */
+ imin = d*n;
+ for (i = 0; i < n; i++)
+ for (j = 0; j < m; j++)
+ if (ai[i][j] > 0 && ai[i][j] < imin)
+ imin = ai[i][j];
+
+ if (abs((double)imin / d - min) > 1e-10)
+ goto next_d;
+
+ /*
+ * Got it! We've found a rational-valued dissection.
+ */
+ printf("min fragment ");
+ print_rational(imin, d);
+ printf(" [%s]\n", VERSION);
+
+ /*
+ * We don't really want to output the matrix, so instead let's
+ * output the ways in which the sticks are cut up.
+ */
+ {
+ int ai2[m][n];
+ for (i = 0; i < n; i++) {
+ for (j = 0; j < m; j++)
+ ai2[j][i] = ai[i][j];
+ }
+ for (i = 0; i < n; i++)
+ qsort(ai+i, m, sizeof(int), compare_ints_1);
+ qsort(ai, n, m*sizeof(int), compare_ints_m);
+ printf(" Cut up %d sticks of length %d like this:\n", n, m);
+ for (i = 0; i < n ;) {
+ for (j = 1; i+j < n && compare_ints_m(ai+i, ai+i+j) == 0; j++);
+ printf(" %d x (", j);
+ for (k = 0; k < m && ai[i][k] > 0; k++) {
+ if (k > 0) printf(" + ");
+ print_rational(ai[i][k], d);
+ }
+ printf(")\n");
+ i += j;
+ }
+
+ for (j = 0; j < m; j++)
+ qsort(ai2+j, n, sizeof(int), compare_ints_1);
+ qsort(ai2, m, n*sizeof(int), compare_ints_n);
+ printf(" Reassemble as %d sticks of length %d like this:\n", m, n);
+ for (j = 0; j < m ;) {
+ for (i = 1; i+j < m && compare_ints_n(ai2+j, ai2+j+i) == 0; i++);
+ printf(" %d x (", i);
+ for (k = 0; k < n && ai2[j][k] > 0; k++) {
+ if (k > 0) printf(" + ");
+ print_rational(ai2[j][k], d);
+ }
+ printf(")\n");
+ j += i;
+ }
+ }
+ return;
+
+ next_d:;