ZOJ Problem Set - 1165
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.
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.
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
The following lines were found:
Source: Zhejiang University Local Contest 2002, Warmup