Programming Assignment 7 - Collinear Points

See the assignment turn-in page (last modified on 22 January 2002) for instructions on turning in your assignment.

typedef std::pair<int, int> point;
std::vector<point> colinear_set(const std::vector<point> &);

that accepts a vector of points and returns a vector of points representing the largest subset of collinear points found in the input vector. Your code may assume the input points are unique. If more than one largest subset exists, the function may return any of them.

You can test your procedure by compiling it with the file

where os is either linux or solaris. The resulting executable reads a list of points from std-in; on eof it computes a maximal collinear point set for the input points. The source file will not be made available because the test program contains my answer to the problem.

You can use the shell script

to generate data for your test executable. gen-lines accepts a single optional, command-line argument to set the random-number seed. Without a command-line seed, gen-lines creates a new set of points each time it's called; gen-lines produces the same set of points for a fixed seed.

Your collinear-set routine should not exploit any knowledge of how gen-lines creates points; I won't be using this routine to test your assignments.

To be correct, your solution must be efficient; that is, you solution should take no more than twice the time my solution takes on the same input vector. The test executable keeps track of execution times.