Given a list of coordinates check if 4 points make a line I was doing some preparation for coding interviews and I came across the following question:


  Given a list of coordinates "x y" return True if there exists a line containing at least 4 of the points (ints), otherwise return False.


The only solution I can think about is in \$O(n^2)\$. It consist of calculating the slope between every coordinate: Given that if \$\frac{y_2-y_1}{x_2 –x_1} = \frac{y_3-y_2}{x_3-x_2}\$  then these three points are on the same line. I have been trying to think about a DP solution but haven't been able to think about one. 

Here is the current code:

def points_in_lins(l):
    length = len(l)
    for i in range(0,length -1):
        gradients = {}
        for j in range(i+1, length):
            x1, y1 = l[i]
            x2, y2 = l[j]
            if x1 == x2:
               m = float("inf")
            else:
               m = float((y2 -y1) / (x2 - x1))
            if m in gradients:
                gradients[m] += 1
                if gradients[m] == 3:
                   return(True)
            else:
                gradients[m] = 1

    return(False)
General remarks


def points_in_lins(l):



The function and argument name can be improved. l is too short and does
not indicate at all that this is a list of points, and points_in_lins
(perhaps you meant points_in_line?) does not indicate that the function
looks for four points in a line.

gradients is in fact a dictionary counting slopes.

Iterating over all pairs of points can be simplified with
enumerate() and slices:

for idx, (x1, y1) in enumerate(l):
    gradients = {}
    for (x2, y2) in l[idx + 1:]:


The “set or increment” for gradients can be simplified with 
defaultdict or a Counter:

gradients = Counter()

# ...

gradients[m] += 1
if gradients[m] == 3:
    return True


The parentheses in return(True) and return(False) are not necessary:

return False


The math

Computing the slope as the quotient

m = (y2 - y1) / (x2 - x1)


requires a separate check for a zero denominator, but is problematic
for another reason: Rounding errors can occur. As an example,

points_in_lins([(0, 300000000000000000), (1, 0), (1, 1), (1, 2)])


evaluates to True: The slopes from the first point to the
other three points all evaluate to the same floating point number.

A possible fix is to compare the “directions” , i.e. the (2-dimensional)
vectors between the two points, normalized in a way such that
two vectors pointing in the same (or opposite direction) are
considered equal.

If all coordinates are integers, then it is best to stick with pure
integer calculations. Normalizing the connecting vector can be
achieved by division by the greatest common divisor of the x- and
y-component, and possibly mirroring it.

Putting it together

from math import gcd
from collections import Counter


def four_points_in_line(points):
    for idx, (x1, y1) in enumerate(points):
        direction_counts = Counter()
        for (x2, y2) in points[idx + 1:]:
            # Compute normalized direction from (x1, y1) to (x2, y2):
            delta_x, delta_y = x2 - x1, y2 - y1
            g = gcd(delta_x, delta_y)
            delta_x, delta_y = delta_x // g, delta_y // g
            if delta_x &lt; 0 or (delta_x == 0 and delta_y &lt; 0):
                 delta_x, delta_y = -delta_x, -delta_y
            # Three identical directions from (x1, y1) means 4 collinear points:
            direction_counts[(delta_x, delta_y)] += 1
            if direction_counts[(delta_x, delta_y)] == 3:
                return True
    return False


It is still a \$ O(n^2) \$ algorithm, but more robust against
rounding and division by zero errors.

If the points are not guaranteed to be distinct then  identical points need have to be treated separately.