#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; }