E. The Amazing Triangle Counting Machine |
Acme Counting Machines has hired you as a consultant to finish their TCM-2000 project. The TCM-2000 is a machine for counting triangles in pictures by means of a video camera attached to a computer. They have already done the easy part of preprocessing the picture to extract the edges and convert the image into a list of segments. Your job is to write a program to count all the non-overlapping triangles defined by those segments. A triangle consists of exactly three segments.
Your program will receive a list of non-intersecting and non-overlapping segments and it has to return the number of non-overlapping triangles in the figure. For example, given the following figure:
Your program would receive the following list of segments: AB, AD, AF, BC, BF, CD, CE, CF, DE and DF. Then, it will have to count the 5 triangles present in the figure, namely: ABF, ADF, BCF, CDE and CDF.
The input format is as follows:
An integer in a single line which says the number of figures that your program will have to process. Then, for each figure there will be:
The output consists of one line for each case, with a single integer number each: the number of triangles found.
1 10 0 0 0 1 0 0 0.5 0.5 0 0 1 0 0 1 0.5 0.5 0 1 0.5 1.5 0 1 1 1 0.5 0.5 1 0 0.5 0.5 1 1 0.5 1.5 1 1 1 0 1 1
5
OMP'09
Facultad de Informatica
Universidad de Murcia (SPAIN)