CareerCup

Here's my solution from leetcode

/**
* 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;
}
};

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()

Read the theory :
[ math.stackexchange.com/questions/20230/maximum-number-of-collinear-points ]
[ stackoverflow.com/questions/4386695/maximum-collinear-points-in-a-plane ]
Finally, the solution.
[ geeksforgeeks.org/count-maximum-points-on-same-line/ ]