This is in java. It has to use merge sort to sort. Write a program that reads N

Question

This is in java. It has to use merge sort to sort.

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.*;
import java.util.*;

public class Main {
public static void sort(int[] a, int low, int high)
{
int N = high - low;   
if (N <= 1)
return;
int mid = low + N/2;
// recursively sort
sort(a, low, mid);
sort(a, mid, high);
// merge two sorted subarrays
int[] temp = new int[N];
int i = low, j = mid;
for (int k = 0; k < N; k++)
{
if (i == mid)
temp[k] = a[j++];
else if (j == high)
temp[k] = a[i++];
else if (a[j]<a[i])
temp[k] = a[j++];
else
temp[k] = a[i++];
}
for (int k = 0; k < N; k++)
a[low + k] = temp[k];   
}
public static void main(String[] args) throws IOException {
try {
   Scanner sc=new Scanner(System.in);
  
   System.out.print("Input total row : ");
    int row = sc.nextInt();

   int [][]arr=new int[row][2];
   int [][]arrs1=new int[row][2];
   int [][]arrs2=new int[row][2];

File file = new File("C:/points.txt"); //creating file
file.createNewFile();
  
   BufferedWriter out = new BufferedWriter(new FileWriter("points.txt")); // taking inputs
   for (int i = 0; i < row ; i++)
       {
           for(int j = 0; j < 2 ; j++)
           {
       arr[i][j] = sc.nextInt();
           out.write("arr[i][j]");
           }
       }
   out.close();
  

       for (int i = 0; i < row ; i++) // For set A
       {
           for(int j = 0; j < 2 ; j++)
           {
       if(j==i)
           arrs1[i][j]=arr[i][j];
             
           }
       }
   sort(arrs1, 0, row);
        System.out.println(" For set A elements after sorting ");
       for (int i = 0; i < row ; i++)       
       {
           for(int j = 0; j < 2 ; j++)
           {
         
           System.out.print( arrs1[i][j] +" ");
             
           }
           System.out.println();
       }      
      
       for (int i = 0; i < row ; i++) // For set B
       {
           for(int j = 0; j < 2 ; j++)
           {
       if(j==i+1)
           arrs2[i][j]=arr[i][j];
             
           }
       }
   sort(arrs2, 0, row);

       System.out.println(" For set B elements after sorting ");
       for (int i = 0; i < row ; i++)       
       {
           for(int j = 0; j < 2 ; j++)
           {
         
           System.out.print( arrs2[i][j] +" ");
             
           }
           System.out.println();
       }      

}
catch(IOException ioe)
{
ioe.printStackTrace();
}
}
}

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.