Discussion:
We all are known to the term slope of a line. It is defined as the change in the y coordinates with respect to the change in the x coordinates of a line. Any amount of changes in y coordinate with respect to x coordinate will make the same slope for a line. That means any two positions (points) that are lying on a straight line will make the same slope.
Suppose, and are two points. These two points can make a straight line. Now, another point will also lie on that line if the slope of and becomes equal to the slope of and . That means, , and will be on same line if .
Using these rules, we can solve this problem. We have to find points that make the same slope as each other. The formula to find slope is:
Here, is the change in y-coordinates and is the change in x-coordinates.
Steps to the solution:
We will go through the first to last points.
We will take one point.
Calculate the slopes it (the point we took) makes with other points. (We must have to keep track of which points are making which slope (because we have to print the points later).
The previous step will give us some slopes. From there, we will identify slopes that are equal or the same.
If we found exactly slopes from the previous step, we can print the points that make this specific slope and end the program. Otherwise, we will take another point and will repeat steps 3 to 5.
Complexity for this solution:
We will calculate slopes for each point. Thus, points will take calculations for worst cases. So we can say the complexity is .