Last Updated: 15 Jan, 2021

Maximum Points On Straight Line

Hard

Asked in companies

Solve now

Problem statement

You are given a 2-D plane, and some 'N' integer coordinates in the form of (X, Y), where 'X' is the x-coordinate and 'Y' is the y-coordinate, all of which lie on that plane. You need to find the maximum number of coordinates among these which can form a straight line.

Note:

1. All the coordinates are integer coordinates.
2. There can be two identical coordinates.

Input Format:

The first line of the input contains an integer 'T', denoting the number of test cases.

The first line of each test case contains the integer 'N', denoting the number of points.

The next N lines of each test case contain 2 space-separated integers which represent the coordinates of a given point.

Output Format:

For each test case, every line of output prints the maximum number of points which lie on a straight line.

Note :

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <=  50
1 <= N <= 10^3
-10^4 <= X, Y <= 10^4

Time Limit: 1 sec

Solve now

Approaches

01 Approach

Algorithm:

Since this is a problem with coordinates and straight lines, we can use the concept of slope of the line to find the answer.
The main idea is to find the slope of one point with all the other points and then find which of these points have the same slope and lie on the same line.
Let the 2D vector ‘POINTS[N][2]’ represent the coordinates of the points that we have.
For each of the coordinates from ‘i’ = 0 to ‘N’ - 1 we can do the following:
- Create a map<double, int> where the key of the map is the slope and the value for each slope will store the number of points with the same slope with the given point.
- Let SAMEPOINT = 0 represent the same overlapped point if there is any overlapped point.
- Let SAMEX = 0 represent the set of coordinates that have the same X coordinates.
- Now for all the points from ‘j’ = 0 to ‘j’ = ‘N’ - 1 do the following:
  - If ‘POINTS[j][0] = ‘POINTS[i][0] and ‘POINTS[j][1] = ‘POINTS[i][1], that means both the points are same, so increment samePoint by 1, i.e. SAMEPOINT = SAMEPOINT += 1.
  - If ‘POINTS[j][0] = ‘POINTS[i][0], then the coordinates have same X coordinates, so increment SAMEX by 1.
  - The slope for each of the set of two points will be slope = (double) (‘POINTS[j][1] - ‘POINTS[i][1]) / (double) (‘POINTS[j][0] - ‘POINTS[i][0]);
  - Now if the slope was not present in the map then we can hash the slope into the map and keep the count as 2.
  - Else we can just increment the count of the slope by 1.
- After exiting from the inner loop we can just iterate through the values of the map and find the maximum frequency and keep on updating the answer.
After the end of this loop we will have the answer.

Solve now