백준 2162 선분그룹(python)

https://www.acmicpc.net/problem/2162

2162번: 선분 그룹

나는 이 문제를 풀기 전에 CCW 알고리즘의 응용 버전인 골드 2 문제, 선분교차 2를 풀었기 때문에 그를 이용하여 쉽게 풀 수 있었다.

 

다음 문제의 아이디어는 다음과 같다.

1.CCW 알고리즘(벡터의 외적)을 이용하여 많은 조건 분기로 선분 교차를 판정하는 함수를 정의한다.

2.Union-Find 자료구조를 활용하여 선분을 통합한다.

3.그룹의 수와 가장 많은 선분을 가진 그룹의 선분 개수를 세준다.

 

코드는 다음과 같다.

def ccw(x1, y1, x2, y2, x3, y3):
    return ((x2-x1)*(y3-y2))-((x3-x2)*(y2-y1))
def subun(x1, y1, x2, y2, x3, y3, x4, y4):
    if ccw(x1,y1,x2,y2,x3,y3)==ccw(x1,y1,x2,y2,x4,y4) == ccw(x3,y3,x4,y4,x1,y1)==ccw(x3,y3,x4,y4,x2,y2) == 0:
        if min(x1, x2) <= x3 <= max(x1, x2) and min(y1, y2) <= y3 <= max(y1, y2):
            return 1
        elif min(x1, x2) <= x4 <= max(x1, x2) and min(y1, y2) <= y4 <= max(y1, y2):
            return 1
        elif min(x3, x4) <= x1 <= max(x3, x4) and min(y3, y4) <= y1 <= max(y3, y4):
            return 1
        elif min(x3, x4) <= x2 <= max(x3, x4) and min(y3, y4) <= y2 <= max(y3, y4):
            return 1
        else: return 0
    elif ccw(x1,y1,x2,y2,x3,y3)*ccw(x1,y1,x2,y2,x4,y4) <= 0 and ccw(x3,y3,x4,y4,x1,y1)*ccw(x3,y3,x4,y4,x2,y2) <= 0:
        return 1
    else:
        return 0
momnode = [i for i in range(3001)]
def find(x):
    if x != momnode[x]:
        momnode[x] = find(momnode[x])
    return momnode[x]
def union(x, y):
    momnode[find(y)] = find(x)
arry = []
n = int(input())
for i in range(n):
    a, b, c, d = map(int, input().split())
    arry.append((a,b,c,d))
for i in range(n):
    for j in range(n):
        if i != j:
            pan = subun(arry[i][0], arry[i][1], arry[i][2], arry[i][3], arry[j][0], arry[j][1], arry[j][2], arry[j][3])
            if pan:
                if find(i) != find(j):
                    union(min(i,j), max(i,j))
cont = 0
for i in range(n):
    if find(i) == i:
        cont += 1
group = [0]*n
for i in range(n):
    group[find(i)] += 1
print(cont)
print(max(group))