2162_선분그룹

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

2162번: 선분 그룹

 

 

 

CCW 알고리즘과 Union find 알고리즘을 같이 사용하면 풀수 있을꺼 같아서 적용하여 풀었다.

 

 

우선 CCW알고리즘을 이용하여 두 선분이교차하는지 하지 않는지 판단하는 함수를 하나 만들고, union find 알고리즘을 활용하여 두 선분이 교차하였다면 한 그룹으로 묶어주는 과정을 진행한다.

 

이때 주의할 점은 parents 배열을 마지막에 꼭 압축해줘야 한다. 같은 그룹안에 있더라도 parents배열이 각 그룹 꼭대기의 조상을 지칭하지 않을 수 있어서 한번 순회하며 find연산으로 부모로 바꿔줘야한다. 해당 과정을 하지 않아서 계속 틀렸었다...

 

 

import sys
input = sys.stdin.readline

def ccw(x1,y1,x2,y2,x3,y3):
    tmp = x1 * y2 + x2 * y3 + x3*y1 -( y1*x2 + y2 * x3 + y3 * x1)
    if tmp > 0:
        return 1
    elif tmp < 0:
        return -1
    else:
        return 0
def check(a,b):
    x1,y1,x2,y2 = a
    x3,y3,x4,y4 = b

    answer = False
    if (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:
        if min(x1, x2) <= max(x3, x4) and min(x3, x4) <= max(x1, x2) and min(y1, y2) <= max(y3, y4) and min(y3,
                                                                                                            y4) <= max(
                y1, y2):
            answer = True
    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:
        answer = True
    return answer

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

n = int(input())
coordinate = [ list(map(int,input().split())) for _ in range(n)]
parents = [ i for i in range(n) ]

for i in range(n):
    for j in range(i+1,n):
        if check(coordinate[i],coordinate[j]) and find(i) != find(j):
            union(i,j)

for i in range(n):
    parents[i] = find(parents[i])
print(len(list(set(parents))))
print(parents.count(max(parents,key = parents.count)))