문제

두 선분의 교점이 존재할 때, 두 선분은 같은 집합으로 매핑된다.
다수의 선분이 주어질 때, 집합의 개수와 크기가 가장 큰 집합에 속한 선분의 개수를 출력한다.

풀이

본 문제를 풀기 위해서는 우선 CCW(Counter-Clock Wise) 알고리즘을 알아야 한다.

CCW 알고리즘을 간단히 정리하자면 다음과 같다.

좌표평면 위에 세 개의 점 A, B, C가 있다고 가정하자.
점 A는 (ax,ay), 점 B는 (bx,by), 점 C는 (cx,cy)처럼 표현할 수 있다.

벡터의 외적을 활용하여 CCW를

처럼 표현할 수 있다.

세 점을 순서대로 연결했을 때의 선이 왼쪽(반시계방향)으로 치우쳐져 있으면 음수, 치우치지 않았다면 0, 오른쪽으로 치우쳐있다면 양수를 반환한다.

이제 문제를 풀기 위해 문제의 조건처럼 4개의 점(A, B, C, D)가 있다고 가정하자. 그리고 점 A, B는 선분 AB를 구성하고, 점 C, D는 선분 CD를 구성한다.

두 선분의 접점이 있다고 가정했을 때, 선분 AB를 기준으로 점 C와 점 D는 각자 다른 방향에 위치해있을 것이다. 또한, 선분 CD를 기준으로 점 A와 점 B는 각자 다른 방향에 위치해있을 것이다.

즉, CCW(A,B,C) * CCW(A,B,D) <= 0이고 CCW(C,D,A) * CCW(C,D,B) <= 0이라면 두 선분은 접점이 존재한다.

왜 굳이 계산을 두 번 하는가?

CCW(A,B,C), CCW(A,B,D)는 선분 AB를 기준으로 점 C, D의 상대적 위치를 구하는 것이고, CCW(C,D,A), CCW(C,D,B)는 선분 CD를 기준으로 점 A, B의 상대적 위치를 구하는 것이다.

모음 'ㅜ'에서 가로획과 세로획이 서로 분리되어 있다고 가정해보자.
세로획을 기준으로 가로획의 양 끝 점은 서로 반대되는 위치(좌, 우)에 존재한다.
그러나 가로획을 기준으로 세로획의 양 끝 점은 같은 위치(아래)에 존재한다.

따라서 각 선분을 기준으로 계산을 해주는 것이다.

예외

CCW(A,B,C) == 0, CCW(A,B,D) == 0, CCW(C,D,A) == 0, CCW(C,D,B) == 0인 경우를 고려해보자.

이 경우 세 가지 경우의 수가 존재한다.

1. 두 선분이 만나지 않는 경우
2. 두 선분이 만나지만, 포함관계가 아닌 경우
3. 두 선분이 만나고 포함관계인 경우

이 경우, 두 선분 중 가장 오른쪽에 있는 점을 포함한 선분의 가장 왼쪽 점과, 나머지 선분의 가장 오른쪽에 있는 점의 위치를 비교해주면 된다.

가령 첫 번째 경우, 가장 오른쪽에 있는 점을 포함한 선분은 CD이며, 이 선분의 가장 왼쪽 점은 C이다. 점 C는 나머지 선분의 가장 오른쪽에 있는 점 B보다 더 오른쪽에 있기 때문에 두 선분은 서로 만나지 않는 것을 확인할 수 있다.

코드

# 선분 그룹

import sys
input = sys.stdin.readline
from collections import deque

num_lines = int(input())
lines = [list(map(int, input().split())) for _ in range(num_lines)]

# 함수 정의
"""
def logger(pre_text = None, **kwargs):

    print(f"====={pre_text}=====")
    for key, value in kwargs.items():
        print(f"{key} : {value}")
    print(f"==========\n")
"""

def outer_product (dota, dotb, dotc):

    ax, ay = dota
    bx, by = dotb
    cx, cy = dotc

    result = (ax*by) + (bx*cy) + (cx*ay) - (bx*ay) - (cx*by) - (ax*cy)
    return result

def is_cross(dota, dotb, dotc, dotd):

    ax, ay = dota
    bx, by = dotb
    cx, cy = dotc
    dx, dy = dotd

    ab_c = outer_product(dota, dotb, dotc)
    ab_d = outer_product(dota, dotb, dotd)

    ab_cd = ab_c * ab_d

    cd_a = outer_product(dotc, dotd, dota)
    cd_b = outer_product(dotc, dotd, dotb)

    cd_ab = cd_a * cd_b

    is_cross_flag = False

    if ab_cd <= 0 and cd_ab <= 0:
        if ab_c + ab_d + cd_a + cd_b == 0: # 전부 0일 경우
            if ay == by:
                x_s = [ax, bx, cx, dx]
            else:
                x_s = [ay, by, cy, dy]

            argmax = max(range(0,4), key = lambda x : x_s[x])
            
            if argmax//2 == 0: # 만약 ab가 더 오른쪽에 있을 경우
                bigger_min = min(x_s[:2])
                smaller_max = max(x_s[2:])
            else:
                bigger_min = min(x_s[2:])
                smaller_max = max(x_s[:2])

            if bigger_min <= smaller_max:
                is_cross_flag  = True

        else:
            is_cross_flag = True

    #print(f"result: {ab_c}, {ab_d}, {cd_a}, {cd_b}")

    return is_cross_flag

# 탐색

queue = deque([0])
not_searched = deque(list(range(1,num_lines)) + [-1]) # 탐색 해야할 선분, -1은 break flag

num_clusters = 0
max_line_in_cluster = 0

# 3중 while문 괜찮나...?

while True:

    num_clusters += 1
    max_line = 1

    while queue: # line_ab 선택

        line_ab_idx = queue.popleft()

        while not_searched: # line_cd 선택

            line_cd_idx = not_searched.popleft()

            if line_cd_idx == -1: # 탈출
                not_searched.append(-1)
                break

            ax, ay, bx, by = lines[line_ab_idx]
            cx, cy, dx, dy = lines[line_cd_idx]

            cross_flag = is_cross((ax,ay), (bx,by), (cx,cy), (dx,dy))

            if cross_flag: # 두 선분이 만날 때
                queue.append(line_cd_idx)
                max_line += 1

            else: # 두 선분이 만나지 않을 때
                not_searched.append(line_cd_idx)

            #logger("third", line_ab = lines[line_ab_idx], line_cd = lines[line_cd_idx],
            #is_cross = cross_flag, num_clusters = num_clusters, max_line = max_line)

            #logger("third", line_ab = line_ab_idx, line_cd = line_cd_idx,
            #is_cross = cross_flag, num_clusters = num_clusters, max_line = max_line)

        # line_cd while문 탈출
        # 군집 내 선분의 개수 비교
        if max_line > max_line_in_cluster:
            max_line_in_cluster = max_line


    # line_ab while문 탈출
    # 새로운 네트워크를 형성해야 함
    new_standard = not_searched.popleft()

    if new_standard == -1: # 더 이상 탐색할 게 없으면 종료
        break

    queue.append(new_standard)

print(num_clusters)
print(max_line_in_cluster)

비고

본 풀이가 있기까지 두 번의 실패를 하였다. 각 실패의 원인을 적어보도록 한다.

실패 1

for i in range(i, len(num_lines)-1):
	for j in range(i+1, len(num_lines)):
    		is_cross (line_ab, line_cd) ...

우선 첫 번째 실패는 두 선분을 비교하는 과정이 너무 많아서 발생하였다. 선분이 총 $n$개 있다고 가정했을 때, $i$번째 선분을 $[i+1,n]$번째 선분과 모두 비교하였다.

파란색 셀을 선분 AB의 index, 초록색 셀을 선분 CD의 index로 표현하였다. 0번 선분은 1~6번 선분과 모두 비교하였다.

효율성을 위해, 이미 교차한다고 판명난 선분은 비교하지 않는 것으로 코드를 수정하였다.

아래 표의 파란색 셀은 기준이 되는 선분, 초록색은 비교를 해야하는 선분, 노란색은 교차된다고 판명된 선분, 회색 선분은 비교가 완료된 선분이다.

우선 0번 선분을 기준으로 기타 나머지 선분에 대해 교차 여부를 계산한다.

그 결과, 1번, 4번, 7번 선분이 교차한다고 하자.
그럼 이제 0번과 교차된 1번 선분에 대해, 교차가 안된 나머지 (2,3,5,6)에 대한 검증을 한다.

1번과 교차하는 선분은 없다. 그럼 이제 4번 선분을 기준으로 나머지 2,3,5,6에 대한 검증을 한다.

새로이 3번 5번 선분과 교차한다. 그럼 이제 발견된 순서대로 7번을 기준으로, 3번을 기준으로, 5번을 기준으로 계속 검사를 한다.

교차되는 선분이 없는 경우, 남은 선분 (2,6)번 중에서 기준점을 잡고 앞서 언급한 과정을 계속 반복한다.

실패 2

if ab_cd <= 0 and cd_ab <= 0:
        if ab_c + ab_d + cd_a + cd_b == 0: # 전부 0일 경우
            x_s = [ax, bx, cx, dx]
            argmax = max(range(0,4), key = lambda x : x_s[x])

앞서 예외 부분에서 네 점이 하나의 직선을 가졌을 경우를 설명했으며, 하나의 직선은 가로축에 평행하다고 가정하여 설명하였다.

그러나 하나의 직선이 세로축에 평행한 경우, 어느 선분이 더 오른쪽에 있는지 판단할 수 없다. 따라서 하나의 직선이 가로축에 평행한지, 세로축에 평행한지 일단 확인해 준 후에, 예외 처리를 해야한다.

추가적으로 python에서는 시간초과가 나기 때문에 pypy로 채점하였다. 채점 기록을 보니 python으로 제출한 사람이 몇 명 있던데, 정말 대단한 것 같다.