코드 작성

1. 주어진 직선에서 교점을 구합니다.

문제 설명에 이미 교점 공식이 주어져 있으므로 이 공식을 이용해 주어진 모든 교점을 구하면 됩니다. for 문이 두 번 중첩되므로 O(n²)이지만, 직선의 개수도 적은 편(1,000개)이고 직선끼리 겹치는 일(무한히 교점이 만들어지는 경우)은 없기 때문에 충분히 작동하리라 예상할 수 있습니다.

for i in range(n):
    a, b, e = line[i]
    for j in range(i + 1, n):
        c, d, f = line[j]
        if a * d == b * c: continue
        x = (b * f - e * d) / (a * d - b * c)
        y = (e * c - a * f) / (a * d - b * c)

주어진 직선의 방정식 개수만큼 for 문을 돌리면서 각 순차마다 방정식의 정보를 얻어온 뒤, 해당 순서의 방정식부터 끝까지 두 방정식의 정보를 공식을 사용해 교점을 구합니다. 시간 복잡도를 구한다면, 횟수가 늘어날수록 전체 반복 횟수가 줄어드는 구조이므로 정도의 연산량이 발생합니다. 즉, ‘O(n²)보다는 조금 더 빠르다’ 정도로 이해하면 됩니다.