## Interview Question

**Country:**United States

A single point will always lie on a line

Two points will always have a line passing through them

So, unless given a single point or two points, we can use the

following strategy to find collinear pointsOnLine

Setup a a triple loop with point variable pt1, pt2 and pt3

Assume pt1, pt2 and pt3 are not the same (or else we may divide by 0)

Find slope using pt1 and pt2

Now pt3 will be collinear with pt1 and pt2 if slope (pt1, pt3) == slope(pt1, pt2)

Be careful with slope values that are very "close" to each other

Some python code below. Not thoroughly tested, and not very optimal!

```
import math
def pointsOnLine(points):
# one single point always can reside on a line
# any two points can also reside a single line
if len(points) <= 2:
return len(points)
max_points_on_line = 0;
for pt1 in points:
for pt2 in points[1:]:
if twoDifferentPoints(pt1, pt2):
slope = (pt2[1] - pt1[1]) / (pt2[0] - pt1[0])
pts = 0;
# (assume) pt1, pt2, and pt3 are different points
# add this check in actual code
for pt3 in points[2:]:
print(pt1, pt2, pt3)
if threeDifferentPoints(pt1, pt2, pt3) and math.isclose(slope, (pt3[1] - pt1[1]) / (pt3[0] - pt1[0])):
pts += 1
if (max_points_on_line < pts):
max_points_on_line = pts;
return max_points_on_line + 2;
def threeDifferentPoints(pt1, pt2, pt3):
return not (pt1[0] == pt2[0] and pt1[1] == pt2[1]
or
pt2[0] == pt3[0] and pt2[1] == pt3[1]
or
pt1[0] == pt3[0] and pt1[1] == pt3[1]
)
def twoDifferentPoints(pt1, pt2):
return not (pt1[0] == pt2[0] and pt1[1] == pt2[1])
def main():
points = [[0, 0], [1, 1], [3, 12],[6,24], [9,36]]
print(pointsOnLine(points))
if __name__ == "__main__":
main()
```

Here's my solution from leetcode

- Abebe August 17, 2017/**

* Definition for a point.

* struct Point {

* int x;

* int y;

* Point() : x(0), y(0) {}

* Point(int a, int b) : x(a), y(b) {}

* };

*/

class Solution {

public:

pair<double,double> SlopeAndnIntercept(Point P1, Point P2)

{

pair<double,double>pair1;

if (P1.x == P2.x)

{

pair1.first = numeric_limits<double>::max();

pair1.second = P1.x;

}

else

{

pair1.first = (double)(P2.y - P1.y) / (double)(P2.x - P1.x);

pair1.second = (double)(P1.y - (double)P1.x*pair1.first);

}

return pair1;

}

int maxPoints(vector<Point>& points) {

if(points.size() == 0) return 0;

if(points.size() == 1) return 1;

if(points.size() == 2) return 2;

double epsilon = 0.000000001;

pair<double, double>pair1;

map<pair<double, double>, int> dic;

for (int i = 0; i < points.size(); i++)

{

int nSame = 0;

bool bFirstSame = false;

for (int l = i + 1; l < points.size(); l++)

{

if (points[l].x == points[i].x && points[i].y == points[l].y)

nSame++;

}

if (nSame == points.size() - 1)

return nSame + 1;

for (int j = i + 1; j < points.size(); j++)

{

if (points[i].x == points[j].x && points[i].y == points[j].y)

{

if (bFirstSame)

continue;

else

bFirstSame = true;

}

pair1 = SlopeAndnIntercept(points[i], points[j]);

if (dic.find(pair1) == dic.end())

dic.insert(make_pair(pair1,2+nSame));

else

continue;

for (int k = j + 1; k < points.size(); k++)

{

if (points[i].x == points[k].x && points[i].y == points[k].y)

{

continue;

}

if(pair1.first == numeric_limits<double>::max() && points[k].x == pair1.second)

dic[pair1]++;

else

{

double temp = (double)abs((pair1.first*(points[k].x) + pair1.second) - points[k].y);

if (temp < epsilon)

dic[pair1]++;

}

}

}

}

int max = dic.begin()->second;

for (auto var = dic.begin(); var != dic.end(); var++)

{

if (var->second > max)

max = var->second;

}

return max;

}

};