백준 - 선분 그룹(2162)

 

올해 푼 문제 중에 가장 어려웠다.

수학적 지식이 필요한 문제인지라

과거 공부에 뜻이 없었던 나에게 상당히 어려웠다.

 

이 문제의 핵심은 ccw 알고리즘이다.

벡터의 외적을 이용해서 선분이 교차하는지 판단할 수 있다.

 

게임에서도 ccw 알고리즘이 많이 쓰인다고 한다.

위치 판별 및 물체 부딪힘 등등

신기하다....

 

선분 (A, B), (C, D)가 있을 경우

CCW(A, B, C)*CCW(A, B, D) < 0 and CCW(C, D, A)*CCW(C, D, A) < 0

가 둘다 -1이 나올 경우 접점이다.

 

예외는

둘다 일직선 상으로 겹치는 경우이다.

둘 다 0일 경우 좌표 위치를 계산해서 겹치는지 판단한다.

 

그리고 그룹을 구해야 하기 때문에 union find를 사용했다.

 

 

 

 

from collections import Counter
def ccw(x1,x2,x3,y1,y2,y3):
    v = x1 * y2 + x2 * y3 + x3 * y1 - x2 * y1 - x3 * y2 - x1 * y3
    if v > 0:
        return 1
    elif v<0:
        return -1
    else:
        return 0

def ccw_cal(x1,y1,x2,y2,x3,y3,x4,y4):
    a = ccw(x1,x2,x3,y1,y2,y3)*ccw(x1,x2,x4,y1,y2,y4)
    b = ccw(x3,x4,x1,y3,y4,y1)*ccw(x3,x4,x2,y3,y4,y2)
    if a == 0 and b == 0:
        if min(x1,x2) <= max(x3,x4) and max(x1,x2) >= min(x3,x4) and min(y1,y2) <= max(y3,y4) and max(y1,y2) >= min(y3,y4):
            return True
    elif a <= 0 and b <= 0:
        return True
    return False

def find(v):
    if parent[v] == v:
        return v
    parent[v] = find(parent[v])
    return parent[v]

def union(i,j):
    a = find(i)
    b = find(j)
    if a == b:
        return
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

data = []
n = int(input())
lines = [list(map(int, input().split())) for _ in range(n)]
parent = [i for i in range(n)]
for i in range(n):
    for j in range(i+1,n):
        x1,y1,x2,y2 = lines[i]
        x3,y3,x4,y4 = lines[j]
        if ccw_cal(x1, y1, x2, y2, x3, y3, x4, y4):
            union(i,j)
for i in range(n):
    parent[i] = find(i)
answer = Counter(parent).most_common()


print(len(answer))
print(answer[0][1])