Could someone help me with this? Thank you! 5. [Collinear Points in a Plane, 50
ID: 3728858 • Letter: C
Question
Could someone help me with this? Thank you!
5. [Collinear Points in a Plane, 50 points] Implement a program that reads N points in a plane and outputs any group of four or more collinear points (i.e., points on the same line) mand line, read the input from Your program should accept an input file the provided file, which contains the number of input points on the first line, followed by two floating-point numbers representing the x-axis and y-axis for a point on each of the following lines. You may assume that all input points are unique. For the provided points.txt input file, your program should then output to the screen the EC330 Applied Algorithms and Data Structures for Engineers, Spring 2018 collinear points in the format specified in the sample output below (Note that you may print the points as floats or doubles). If there is more than a single group of collinear points, you should separate the groups with an empty line. The ordering of the points within each group does not matter Sample points.txt file (provided), which describes the set of points (1,4.5), (3,4), 1 4.5 1-1 Sample output for the above input: (0,0) (2,2) (4,4)Explanation / Answer
Since the language was not specifies, the below program is in c++.
However the logic can be applied to any language.
/** Let the points be stored in a[n][2] where n is number of points.
So a[0][0] is the x-coordinate of the first point, and a[0][1] is the y - coordinate of the first point and so on.
int temp[n] is a temporary array that stores the indices of collinear points
int count stores number of elements in temp ( to check if it is greater than 4)
bool used[n] stores a boolean value indicating if the point has already been printed. **/
int temp[n],count;
bool used[n];
/**We iterate i from 1 to n-2, j from i+1 to n-1 and k from j+1 to n. This way, every combination of 3 points is covered. Essentially, we choose three points from the list of points. if the area of the triangle formed by these three points is 0, then we know that they are collinear. **/
for(int i=0;i<n-2;i++)
{
for(int j=i+1;j<n-1;j++)
{
count=2;int q=2; //the number of points is currently 2. 'q' is a variable used to access the next free space in temp.
temp[0]=i; temp[1]=j; //points i and j are obviously collinear to each other, and are stored in temp.
for(int k=j+1;k<n;k++)
{
if(!used[k]) //check if the point k has already been printed
{
if(area(a[i][0],a[i][1],a[j][0],a[j][1],a[k][0],a[k][1])==0) //if the area of the triangle formed by points i,j,k is 0
{
temp[q++]=k; //then k is added to temp
count++;
}
}
}
if(count>=4)
{
for(int l=0;l<count;l++)
{
cout<<a[temp[l]][0]<<" "<<a[temp[l]][1]<<endl; //print statement
used[temp[l]]=1;
}
cout<<endl; //skip a line after every set of collinear points
}
}
}
Function to find area of triangle:
double area(double x1,double y1,double x2,double y2,double x3,double y3)
{
return abs((x1-x2)*(y2-y3)-(x2-x3)*(y1-y2));
}