Problem 1
Counting Triangles
Input file: data1.txt
This is a game of counting triangles. Short sticks of 1 or2units of length are placed onto a grid as shown in Figure 1, horizontally, vertically or diagonally. The sticks placed diagonally are allowed to cross each other.
Figure 1: Basic placement patterns of sticks.
A random placement of short sticks on a grid creates either a pattern without any triangle or a pattern with one or more triangles in Figure 2 where patterns (a), (b), (c), (d) and (e) have 2, 5, 12, 0 and 0 triangles respectively.
Figure 2: Sample patterns of triangles.
Your task is to write a program that counts the number of triangles in a pattern.
Input
The input file consists of one or more patterns of short sticks. The first line of each pattern contains the name of the pattern. Each name is an alphanumeric string of no more than 30 characters. The next line contains the number of short sticks to be placed on the grid. This is followed by pairs of integers specifying the starting and ending coordinates of each stick. The grid will not be larger than 10 by 10; i.e., the coordinates of the lower left and upper right corners are (0, 0) and (9, 9) respectively.
- 1 -
Output
For each pattern, the output file contains a line with the name of the pattern followed by the number of triangles found. Sample inputs and outputs for Figures 2(a) and 2(e) are illustrated below.
Sample Input
Figure2(e)
2
1 1 2 2 2 2 3 1
Sample Output
Figure2(e) 0 triangles