Check for 3 points in the same line given coordination python

yeet 0
Viewed 19

Given the coordination of points, check if any 3 points is in a straight line (first input is the number of point), I know that somebody has asked this before, but it's still unclear

here's my approach

n = int(input())
a = []
for i in range(n):
     a.append([int(v) for v in input().split()])
b = []
for lst in a:
    b.extend(lst)
rows = []
cols = []
for i in range(1, len(b)+1, 2):
    cols.append(b[i-1])
for i in range(2, len(b)+2, 2):
    rows.append(b[i-1])
count = 0    
for i in range(len(b)):
    for j in range(i+1, 8):
        for _ in range(j+1, 0):
            if rows[i] == rows[j] == rows[_] or cols[i]==cols[j]==cols[_] or abs(rows[i]-rows[j]-rows[_])==abs(cols[i]-cols[j]-cols[_]):
                count += 1
if count >= 3:
    print("Yes")
else:
    print("No")

example inputs: 1

4
0 1
0 2
0 3
1 1

2

14
5 5
0 1
2 5
8 0
2 1
0 0
3 6
8 6
5 9
7 9
3 4
9 2
9 8
7 2

if there're any different approach, feel free to comment

point coordinates list python
1 Answers

Here is one approach.

from collections import defaultdict
from itertools import combinations
from fractions import Fraction

def slope(pair):
    (x1, y1), (x2, y2) = pair
    dy = y2 - y1
    dx = x2 - x1
    if dx == 0:
        return None
    else:
        return Fraction(dy, dx)

def components(pair_list):
    # Disjoint set union/find data structure
    parent = {point: point for pair in pair_list for point in pair}
    size = {point: 1 for point in parent}
    for p1, p2 in pair_list:
        # p1 = Find(p1)
        while parent[p1] != p1:
            p1, parent[p1] = parent[p1], parent[parent[p1]]
        # p2 = Find(p2)
        while parent[p2] != p2:
            p2, parent[p2] = parent[p2], parent[parent[p2]]
        if p1 == p2:
            continue
        # Union (by size)
        if size[p1] < size[p2]:
            p1, p2 = p2, p1
        parent[p2] = p1
        size[p1] += size[p2]
    
    components = defaultdict(list)
    for p in parent:
        # q = Find(p)
        q = p
        while parent[q] != q:
            q, parent[q] = parent[q], parent[parent[q]]
        components[q].append(p)
    
    return list(components.values())

def colinear_segments(points):
    point_pairs_by_slope = defaultdict(list)
    for pair in combinations(points, 2):
        point_pairs_by_slope[slope(pair)].append(pair)
    
    for pair_list in point_pairs_by_slope.values():
        if len(pair_list) >= 2:
            for component in components(pair_list):
                if len(component) > 2:
                    yield component

def main():
    n = int(input())
    points = []
    for _ in range(n):
        x, y = map(int, input().split())
        points.append((x, y))

    for component in colinear_segments(points):
        print(component)

if __name__ == "__main__":
    main()

You can figure out all of the pairs of points with the same slope. Then you can group them together into components (since if AB and BC have the same slope and both contain B, then ABC are colinear).

On your first input, this outputs [(0, 1), (0, 2), (0, 3)], and on the second input, this does not print anything.

This is quadratic (sort of, union/find is so fast as to be pretty much constant time per loop, but do a DFS or BFS instead if you care) time in the number of input points. I don't know if it's possible to do any better, but maybe.

Here's an extra example:

Input: (3x3 grid)
9
0 0
0 1
0 2
1 0
1 1
1 2
2 0 
2 1
2 2
Output: (three rows, three columns, two diagonals)
[(0, 0), (0, 1), (0, 2)]
[(1, 0), (1, 1), (1, 2)]
[(2, 0), (2, 1), (2, 2)]
[(0, 0), (1, 0), (2, 0)]
[(0, 1), (1, 1), (2, 1)]
[(0, 2), (1, 2), (2, 2)]
[(0, 0), (1, 1), (2, 2)]
[(0, 2), (1, 1), (2, 0)]
useroA5M0
Related