// triangles.cpp // by William A. McKee // Oct. 17, 2004 // To compile with MSVC7: cl /GX triangles.cpp #include // data used to determine if the vertices are colinear #define NUMBER_OF_LINES 6 #define NUMBER_OF_VERTICES_PER_LINE 4 int lines [NUMBER_OF_LINES][NUMBER_OF_VERTICES_PER_LINE] = { 0, 2, 4, 6, 0, 3, 7, 9, 0, 5, 8, 10, 1, 2, 3, 5, 1, 4, 7, 8, 1, 6, 9, 10, }; inline bool in_line (int line, int vertice) { // check each vertice in the line for (int i = 0; i < NUMBER_OF_VERTICES_PER_LINE; i++) // if we find one, we are done if (lines [line] [i] == vertice) return true; // otherwise, no luck return false; } inline bool colinear (int a, int b) { // exclude the case where the vertices are equal if (a == b) return false; // special case for bottom line of triangle P0 - P1 if (a <= 1 && b <= 1) return true; // for each line for (int i = 0; i < NUMBER_OF_LINES; i++) // check if the two points are colinear if (in_line (i, a) && in_line (i, b)) return true; // otherwise, they are not colinear return false; } inline bool triangle (int a, int b, int c) { return colinear (a, b) && colinear (b, c) && colinear (a, c); } inline bool colinear (int a, int b, int c) { // for each line for (int i = 0; i < NUMBER_OF_LINES; i++) // see if the three points are colinear if (in_line (i, a) && in_line (i, b) && in_line (i, c)) return true; // otherwise they are not colinear return false; } int main () { int count = 0; // brute-force: try all unique combinations of vertices for (int i = 0; i <= 10; i++) for (int j = i+1; j <= 10; j++) for (int k = j+1; k <= 10; k++) // if the vertices form a triangle and they are not colinear if (triangle (i, j, k) && ! colinear (i, j, k)) // then count it as a valid solution count++; // output the result std::cout << count << std::endl; }