Given a list of distinct points [x, y] with integer coordinates, write max_points(points: list[list[int]]) -> int returning the largest number of them that lie on a single straight line.
Checking every pair of points against every third point is O(n³), too slow for the largest tests; aim for about O(n² log C), where C bounds the coordinates.
max_points([[1, 1], [2, 2], [3, 3]]) # 3
max_points([[1, 1], [3, 2], [5, 3], [4, 1], [2, 3], [1, 4]]) # 4 ([3,2], [4,1], [2,3], [1,4])
max_points([[0, 0]]) # 1
Constraints: 1 ≤ len(points) ≤ 500 in Python (up to 2,500 in C++ and Java, so that O(n³) is too slow there as well), -10^9 ≤ x, y ≤ 10^9, all points distinct.
Show hint
Fix one anchor point and group every other point by the direction from the anchor to it: points sharing a direction are collinear with the anchor. The trap is representing a direction exactly. Float slopes break on vertical lines and round nearly equal slopes together; reduce (dx, dy) by their gcd and normalise the sign instead.