This is in java. Also use merge sort to first sort the numbers in the array. Wri
ID: 3814744 • Letter: T
Question
This is in java. Also use merge sort to first sort the numbers in the array.
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)
Explanation / Answer
import java.io.File;
import java.io.FileNotFoundException;
import java.util.*;
public class CollinearPoints {
class Point {
int x;
int y;
Point(int x, int y) {
this.x = x;
this.y = y;
}
}
public static void main(String args[]) throws Exception {
List<Point> points;
CollinearPoints cp = new CollinearPoints();
//Read points from file points.txt
points = cp.readPointsFromFile(new File("points.txt"));
if(points == null){
return;
}
//Sort based on the difference among points
cp.sortPoints(points);
//Print collinear points
cp.printCollinearPoints(points);
}
private void printCollinearPoints(List<Point> points) {
int diff = points.get(0).x - points.get(0).y;
int set = 0;
int init = 0;
int fin = 1;
for(int i=1; i<points.size();i++) {
if(diff == points.get(i).x - points.get(i).y) {
fin++;
}else{
if(fin - init>=3) {
set++;
System.out.print("Set "+ set + "( " + (fin - init + 1) + " Points" + "):");
for(int j = init;j<=fin; j++){
System.out.print("(" + points.get(j).x +", "+ points.get(j).y + ") ");
}
System.out.println();
}
diff = points.get(i).x - points.get(i).y;
init = i;
fin = i;
}
}
}
private void sortPoints(List<Point> points) {
Collections.sort(points, new Comparator<Point>() {
@Override
public int compare(Point p1, Point p2) {
int diff = (p1.x-p1.y) - (p2.x-p2.y);
if(diff == 0){
return p1.x - p2.x;
}
return diff;
}
});
}
private List<Point> readPointsFromFile(File file) {
List<Point> points = new ArrayList<>();
if (!file.exists()) {
System.out.println("points.txt File not Found is same directory");
return null;
}
Scanner scanner = null;
try {
scanner = new Scanner(file);
} catch (FileNotFoundException e) {
e.printStackTrace();
return null;
}
int x=0;
int y=0;
while (scanner.hasNext()) {
String string = scanner.next();
String array[] = string.split("[(),]");
Point point;
if(array.length == 2){
x = Integer.parseInt(array[1]);
}else if(array.length == 1){
y = Integer.parseInt(array[0]);
points.add(new Point(x, y));
}
}
return points;
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.