교점에 별 만들기

• 그냥 시키는 대로 구현하면 되는 문제.
• 각 line 쌍에 대해서 공식대로 교점을 구하고, 교점의 좌표가 정수이면 저장해둔다. 이렇게 구해둔 교점의 좌표들중 x좌표와 y좌표의 최솟값과 최댓값을 구해서 그 크기만큼 2차원 배열을 .으로 채우고, 교점의 위치에 *을 저장하면 끝.
• 시간 복잡도는 모든 line 쌍에 대해서 교점을 구해야 하므로 O(n^2). 그리고 결과로 나오는 사각형의 크기가 최대 O(x*y)이므로 출력에 (x*y)가 필요하다. 총 시간 복잡도는 O(n^2 + x*y)

"""Solution code for "Programmers 87377. 교점에 별 만들기".

- Problem link: https://programmers.co.kr/learn/courses/30/lessons/87377
- Solution link: http://www.teferi.net/ps/problems/programmers/87377
"""

import itertools


def solution(line):
    intersect_x_points, intersect_y_points = [], []
    for (a, b, e), (c, d, f) in itertools.combinations(line, 2):
        if (denom := a * d - b * c) == 0:
            continue
        x, r1 = divmod(b * f - e * d, denom)
        y, r2 = divmod(e * c - a * f, denom)
        if r1 == r2 == 0:
            intersect_x_points.append(x)
            intersect_y_points.append(y)
    min_x, max_x = min(intersect_x_points), max(intersect_x_points)
    min_y, max_y = min(intersect_y_points), max(intersect_y_points)
    grid = [['.'] * (min_x - max_x + 1) for _ in range(min_y - max_y + 1)]
    for x, y in zip(intersect_x_points, intersect_y_points):
        grid[y - min_y][x - min_x] = '*'
    return [''.join(row) for row in grid]