[BOJ 2162] 선분 그룹

문제

---

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

풀이

---

선분 교차 2에서의 선분 교차 판별 코드에 disjoint set을 결합하면 된다.

코드

---

import sys


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


def isintersect(x1, y1, x2, y2, x3, y3, x4, y4):
    res1 = ccw(x1, y1, x2, y2, x3, y3)
    res2 = ccw(x1, y1, x2, y2, x4, y4)
    res3 = ccw(x3, y3, x4, y4, x1, y1)
    res4 = ccw(x3, y3, x4, y4, x2, y2)

    if res1 == res2 == res3 == res4 == 0:
        if (max(x1, x2) < min(x3, x4)) or (max(x3, x4) < min(x1, x2)) or (max(y1, y2) < min(y3, y4)) or (max(y3, y4) < min(y1, y2)):
            return 0
        else:
            return 1

    elif (res1 * res2 <= 0) and (res3 * res4 <= 0):
        return 1
    else:
        return 0


def union(x, y):
    x = find(x)
    y = find(y)
    if x > y:
        x, y = y, x
    parent[x] = y


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


n = int(sys.stdin.readline())
parent = [i for i in range(n)]
coord = [tuple(map(int, sys.stdin.readline().split())) for _ in range(n)]
group = n

for i in range(n):
    for j in range(i + 1, n):
        if isintersect(*coord[i], *coord[j]) and (find(i) != find(j)):
            union(i, j)
            group -= 1

count = [0] * n
for i in range(n):
    count[find(i)] += 1

print(group)
print(max(count))