Solved: Write a program that reads N points….
Write a program that reads N points, specified by their 2D coordinates, and outputs any set of four or more collinear points (i.e., points on the same line). The obvious brute-force algorithm requires O(N4) time. However, there is a better algorithm that makes use of sorting and runs in O(N2 log N) time (Merge Sort).
Your program should read input from a text file called points.txt that is in the same directory as your java source and class files. The file should contain the coordinates of a set of points in the format shown below:
(2, 3) (4, 4) (-1, 2) (1, 0) (10, 10) (-1, 0) (3, 3) (-1, -1) (0, 1) (7, 5) (7, 8) (-4, 5) (9, 10)
You must use the name “points.txt” for your input file and you can hardcode the filename in your Java program. For testing we will use different sets of points in a file with the same name – “points.txt”.
The x and y coordinates of the points can be integers only.
Your program should calculate if there are any sets of four or more points that lie on the same line and output the sets. In the above example, there is a set of four points that lie on the line y = x, and, another set of five other points, that line on the line y = x+1. There is another set of four collinear points too – you could find that out.
Your program should determine these collinear point sets and output them in the format shown below. Note that in each set, points are sorted by their x-axis value.
Found these sets of four of more collinear points:
Set 1 (4 points): (-1, -1) (3, 3) (4, 4) (10, 10)
Set 2 (5 points): (-1, 0) (0, 1) (2, 3) (7, 8) (9, 10)