#include
/*
* Each point numbered from 0 to 10 has a corresponding incidence mask. The
* idea is that by unioning these incidence masks we can have a
* representation of lines, line collections or other point sets.
*/
#define P0 (1 << 0)
#define P1 (1 << 1)
#define P2 (1 << 2)
#define P3 (1 << 3)
#define P4 (1 << 4)
#define P5 (1 << 5)
#define P6 (1 << 6)
#define P7 (1 << 7)
#define P8 (1 << 8)
#define P9 (1 << 9)
#define P10 (1 << 10)
/*
* For each point, there is a set of points that can be reached with an edge
* as described in the original problem.
*/
int lineMask[11] = {
/* 0 */ P1 | P2 | P3 | P4 | P5 | P6 | P7 | P8 | P9 | P10,
/* 1 */ P0 | P2 | P3 | P4 | P5 | P6 | P7 | P8 | P9 | P10,
/* 2 */ P0 | P4 | P6 | P1 | P3 | P5,
/* 3 */ P0 | P7 | P9 | P1 | P2 | P5,
/* 4 */ P0 | P2 | P6 | P1 | P7 | P8,
/* 5 */ P0 | P8 | P10 | P1 | P2 | P3,
/* 6 */ P0 | P2 | P4 | P1 | P9 | P10,
/* 7 */ P0 | P3 | P9 | P1 | P7 | P8,
/* 8 */ P0 | P5 | P10 | P1 | P4 | P7,
/* 9 */ P0 | P3 | P7 | P1 | P6 | P10,
/* 10 */ P0 | P5 | P8 | P1 | P6 | P9
};
/*
* The problem with just finding a 3 points with edges between each pair is
* that collinear solutions are also given. So we just list the colinear
* line sets so that any triplet that is colinear would necessarily be a
* subset of one of these.
*/
int colinear[7] = {
P0 | P1,
P0 | P2 | P4 | P6,
P0 | P3 | P7 | P9,
P0 | P5 | P8 | P10,
P1 | P2 | P3 | P5,
P1 | P4 | P7 | P8,
P1 | P6 | P9 | P10
};
/*
* Obviously the above structures could be initialized in a dynamic way. I
* just hard coded them in a natural way that should be easy to understand.
*/
int count () {
int v0, v1, v2, i, j;
int c = 0;
/* Iterate over all possible 3 different points in an ordered way. */
for (v0 = 0; v0 < 11; v0 ++) {
for (v1 = v0 + 1; v1 < 11; v1++) {
for (v2 = v1 + 1; v2 < 11; v2++) {
/* Check that the three points have lines between each pair. */
if ((lineMask[v0] & (1 << v1)) != 0
&& (lineMask[v0] & (1 << v2)) != 0
&& (lineMask[v1] & (1 << v2)) != 0) {
/* Check that the points are not colinear. */
j = (1 << v0) | (1 << v1) | (1 << v2);
for (i=0; i < 7; i++) {
if ((colinear[i] | j) == colinear[i]) break;
}
if (i < 7) continue;
/* Ok, this must be a valid triangle. */
printf ("%2d, %2d, %2d\n", v0, v1, v2);
c++;
}
}
}
}
return c;
}
int main () {
int c = count ();
printf ("%d triangles\n", c);
return 0;
}