| Laser Lines |
A computer chip manufacturer has discovered a new way to combine opto-electronics and ordinary electronics by forming light-emitting and receiving nodes on the surface of the chip. These can be used to send messages to each other in a direct line-of-sight manner, thereby speeding up operation considerably by allowing a much greater density of information transfer. One difficulty is that the nodes must all be able to send messages to each other; no node should block the line-of-sight between two other nodes. The manufacturing method ensures that the nodes will be positioned exactly on the points of a lattice covering the chip, so their coordinates are given by integers between 0 and 9999 (inclusive) except that for technical reasons no node can appear at point (0, 0).
Write a program that will read in sets of coordinates of these nodes and determine whether any of them lie on lines containing three or more nodes. Because of the layout method used, it is envisaged that there may well be several lines containing three nodes, but that `longer' lines will be increasingly rare. However, no line will contain more than 10 points.
Input will consist of a series of data sets, each set containing the coordinates of between 3 and 300 points (both inclusive). Each set will start on a new line.
The coordinates will be pairs of integers in the range 0 to 9999 and each set will be terminated by a pair of zeroes (0 0). Successive numbers will be separated by one or more spaces; in addition a data set may be split into several lines, such splits will only occur between coordinate pairs and never between the elements of a coordinate pair. The entire file will also be terminated by a pair of zeroes (0 0).
Note that there will be several test cases, but only one will contain more than 100 points.
Output, for each set, is either the message "No lines were found", or the message "The following lines were found:", followed by the sets of points lying on straight lines, each set ordered first by x, and if the x's are equal, then by y.
All coordinates are in a field of width 4, and are separated by a comma; the points are delimited by brackets, with no spaces between successive points. The lines themselves are ordered in a similar manner to the points on each line; i.e. by considering the first point on each line, and if more than one line starts at that point, by considering the second point on the line.
5 5 8 7 14 11 4 8 20 15 12 6 18 21 0 0 5 5 8 8 14 13 0 0 5 5 25 17 20 23 10 11 20 14 15 11 0 0 0 0
The following lines were found: ( 4, 8)( 8, 7)( 12, 6) ( 5, 5)( 8, 7)( 14, 11)( 20, 15) ( 12, 6)( 14, 11)( 18, 21) No lines were found The following lines were found: ( 5, 5)( 10, 11)( 20, 23) ( 5, 5)( 15, 11)( 20, 14)( 25, 17)