[백준]_2162번 : 선분 그룹(파이썬)

2162번: 선분 그룹

 

두 선분 A, B가 교차한다는 사실을 다른 관점에서 해석해 본다면 노드 A, B가 연결되어 있다고 해석할 수 있다. 그리고 노드들의 연결을 관점에서 그룹의 개수와 가장 큰 그룹의 요소의 개수는 분리 집합으로 다시 풀릴 수 있다. 

 

선분의 교차는 CCW알고리즘으로 해결할 수 있다. 즉 가능한 모든 선분 조합을 비교해보면서 교차하면 분리 집합을 이용해 부모 선분을 찾게 해 주면 된다. 

 

아이디어 자체는 굉장히 간단하지만 마지막 경로 압축 부분까지 꼼꼼히 챙겨주어야 한다.

 

최종 코드>>

import sys
from collections import Counter

input = sys.stdin.readline


class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y


class Line:
    def __init__(self, p1: Point, p2: Point):
        self.p1 = p1
        self.p2 = p2


line_repo = []
n = int(input())
for _ in range(n):
    x1, y1, x2, y2 = map(int, input().split())
    line_repo.append(Line(Point(x1, y1), Point(x2, y2)))


def intersect(l1: Line, l2: Line):
    x1, x2, x3, x4, y1, y2, y3, y4 = l1.p1.x, l1.p2.x, l2.p1.x, l2.p2.x, l1.p1.y, l1.p2.y, l2.p1.y, l2.p2.y

    def ccw(x1, y1, x2, y2, x3, y3):
        return x1 * y2 + x2 * y3 + x3 * y1 - x2 * y1 - x3 * y2 - x1 * y3

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


parent = [*range(n)]


def find(x):
    if parent[x] != x:
        return find(parent[x])
    return x


def union(a, b):
    a = find(a)
    b = find(b)
    if a > b:
        parent[a] = b
    else:
        parent[b] = a


for i in range(n):
    for j in range(i + 1, n):
        if intersect(line_repo[i], line_repo[j]):
            union(i, j)
parent = [find(x) for x in parent]
ans = Counter(parent)
print(f"{len(ans)}\n{max(ans.values())}")