Solution: Label all the vertices as 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 from top to bottom, left to right.
There are 7 lines, each line with a few vertices on it.
Line 1: {0, 1, 7},
Line 2: {0, 2, 6, 8},
Line 3: {0, 3, 5, 9},
Line 4: {0, 4, 10},
Line 5: {1, 2, 3, 4},
Line 6: {4, 5, 6, 7},
Line 7: {7, 8, 9, 10}.
We examine all triples, and check whether three vertices form a valid triangle:
- These vertices cannot all lie on the same line.
- Each pair of these vertices should lie on the same line.
Output of the following Java code:
Triangle 1: (0, 1, 2)
Triangle 2: (0, 1, 3)
Triangle 3: (0, 1, 4)
Triangle 4: (0, 2, 3)
Triangle 5: (0, 2, 4)
Triangle 6: (0, 3, 4)
Triangle 7: (0, 4, 5)
Triangle 8: (0, 4, 6)
Triangle 9: (0, 4, 7)
Triangle 10: (0, 5, 6)
Triangle 11: (0, 5, 7)
Triangle 12: (0, 6, 7)
Triangle 13: (0, 7, 8)
Triangle 14: (0, 7, 9)
Triangle 15: (0, 7, 10)
Triangle 16: (0, 8, 9)
Triangle 17: (0, 8, 10)
Triangle 18: (0, 9, 10)
Triangle 19: (1, 4, 7)
Triangle 20: (2, 4, 6)
Triangle 21: (3, 4, 5)
Triangle 22: (4, 7, 10)
Triangle 23: (5, 7, 9)
Triangle 24: (6, 7, 8)
Code in Java: (still need to figure out the best way to paste code here)
public void countTriangles() { int[][] linesAdjArray = new int[][] { {0, 1, 7}, {0, 2, 6, 8}, {0, 3, 5, 9}, {0, 4, 10}, {1, 2, 3, 4}, {4, 5, 6, 7}, {7, 8, 9, 10}, }; int numTriangles = 0; int numVectices = 11; for (int i = 0; i < numVectices - 2; i++) { for (int j = i + 1; j < numVectices - 1; j++) { for (int k = j + 1; k < numVectices; k++) { if ( !isCollinear(linesAdjArray, i, j, k) && isConnected(linesAdjArray, i, j) && isConnected(linesAdjArray, i, k) && isConnected(linesAdjArray, j, k) ) { numTriangles++; String triangleInfo =
"Triangle " + numTriangles + ": " + "(" + i + ", " + j + ", " + k + ")"; System.out.println(triangleInfo); } } } } return; } public boolean isCollinear( int[][] linesAdjArray, int a, int b, int c ) { for (int[] lineAdjArray : linesAdjArray) { if ( Arrays.binarySearch(lineAdjArray, a) >= 0 && Arrays.binarySearch(lineAdjArray, b) >= 0 && Arrays.binarySearch(lineAdjArray, c) >= 0 ) { return true; } } return false; } public boolean isConnected( int[][] linesAdjArray, int a, int b ) { for (int[] lineAdjArray : linesAdjArray) { if ( Arrays.binarySearch(lineAdjArray, a) >= 0 && Arrays.binarySearch(lineAdjArray, b) >= 0 ) { return true; } } return false; }
No comments:
Post a Comment