Ax + By + C = 0으로 표현할 수 있는 n개의 직선이 주어질 때,
이 직선의 교점 중 정수 좌표에 별을 그리려 합니다.
예를 들어, 다음과 같은 직선 5개를
2x - y + 4 = 0
-2x - y + 4 = 0
-y + 1 = 0
5x - 8y - 12 = 0
5x + 8y + 12 = 0
좌표 평면 위에 그리면 아래 그림과 같습니다.
이때, 모든 교점의 좌표는 (4, 1), (4, -4), (-4, -4), (-4, 1), (0, 4), (1.5, 1.0), (2.1, -0.19), (0, -1.5), (-2.1, -0.19), (-1.5, 1.0)입니다. 이 중 정수로만 표현되는 좌표는 (4, 1), (4, -4), (-4, -4), (-4, 1), (0, 4)입니다.
만약 정수로 표현되는 교점에 별을 그리면 다음과 같습니다.
위의 그림을 문자열로 나타낼 때, 별이 그려진 부분은 *, 빈 공간(격자선이 교차하는 지점)은 .으로 표현하면 다음과 같습니다.
"..........."
".....*....."
"..........."
"..........."
".*.......*."
"..........."
"..........."
"..........."
"..........."
".*.......*."
"..........."
이때 격자판은 무한히 넓으니 모든 별을 포함하는 최소한의 크기만 나타내면 됩니다.
따라서 정답은
"....*...."
"........."
"........."
"*.......*"
"........."
"........."
"........."
"........."
"*.......*"
입니다.
직선 A, B, C에 대한 정보가 담긴 배열 line이 매개변수로 주어집니다. 이때 모든 별을 포함하는 최소 사각형을 return 하도록 solution 함수를 완성해주세요.
import math
def intersection(A, B, C, D, E, F):
denom = A * D - B * C
if denom == 0:
return None, None
x = (B * F - E * D) / denom
y = (E * C - A * F) / denom
if x == int(x) and y == int(y):
return int(x), int(y)
else:
return None, None
def solution(line):
points = set()
inf = math.inf
x_min, x_max, y_min, y_max = inf, -inf, inf, -inf
for i in range(len(line) - 1):
for j in range(i + 1, len(line)):
A, B, E, C, D, F = line[i] + line[j]
x, y = intersection(A, B, C, D, E, F)
if x == None:
continue
points.add((x, y))
x_min = min(x, x_min)
x_max = max(x, x_max)
y_min = min(y, y_min)
y_max = max(y, y_max)
arr = [['.' for _ in range(x_max - x_min + 1)]
for _ in range(y_max - y_min + 1)]
for x, y in points:
arr[y_max - y][x - x_min] = '*'
return [''.join(elem) for elem in arr]