Most Points on One Line

Write max_points_on_line(points) that returns the largest number of points from the list that lie on one straight line. Each point is [x, y] with integer coordinates, and the line can be at any angle, including vertical and horizontal.

The same point can appear more than once. Every copy counts, and copies of one point lie on every line through it.

Examples

max_points_on_line([[1, 1], [2, 2], [3, 3]])
# returns 3

max_points_on_line([[1, 1], [3, 2], [5, 3], [4, 1], [2, 3], [1, 4]])
# returns 4

max_points_on_line([[0, 0], [0, 0], [1, 1]])
# returns 3

max_points_on_line([])
# returns 0

In the second example [3, 2], [4, 1], [2, 3] and [1, 4] all lie on the line x + y = 5.

Constraints

• 0 <= len(points) <= 300
• Coordinates are integers between -10**9 and 10**9

Note

Coordinates can be very large, so watch out for rounding errors.