난이도
문제
N개의 선분들이 2차원 평면상에 주어져 있다. 선분은 양 끝점의 x, y 좌표로 표현이 된다.
두 선분이 서로 만나는 경우에, 두 선분은 같은 그룹에 속한다고 정의하며, 그룹의 크기는 그 그룹에 속한 선분의 개수로 정의한다. 두 선분이 만난다는 것은 선분의 끝점을 스치듯이 만나는 경우도 포함하는 것으로 한다.
N개의 선분들이 주어졌을 때, 이 선분들은 총 몇 개의 그룹으로 되어 있을까? 또, 가장 크기가 큰 그룹에 속한 선분의 개수는 몇 개일까? 이 두 가지를 구하는 프로그램을 작성해 보자.
입력
첫째 줄에 N(1 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N+1번째 줄에는 양 끝점의 좌표가 x1, y1, x2, y2의 순서로 주어진다. 각 좌표의 절댓값은 5,000을 넘지 않으며, 입력되는 좌표 사이에는 빈칸이 하나 있다.
출력
첫째 줄에 그룹의 수를, 둘째 줄에 가장 크기가 큰 그룹에 속한 선분의 개수를 출력한다.
예제
| 입력 | 출력 |
|---|---|
| 3 1 1 2 3 2 1 0 0 1 0 1 1 | 1 3 |
| 3 -1 -1 1 1 -2 -2 2 2 0 1 -1 0 | 2 2 |
풀이
우선 이 문제를 풀기 위해서는 CCW 알고리즘을 알아야 한다.
선분 교차 알고리즘인 CCW(CounterClockWise) 알고리즘을 이용한다.
좌표 평면 위의 점 세개를 이용하여 각 선분이 교차 하는지, 평행한지, 교차 하지 않는지를 판단할 수 있다.
선분 와 선분 가 있을 때,
점 , 점 , 점 를 이었을 때 반시계 방향인 경우, 시계 방향인 경우, 평행한 경우로 나뉘어진다.
이것을 CCW 알고리즘에서 삼각형 면적 구하는 공식 + 벡터를 이용하여 구한다.
의 공식으로 구할 수 있으며
- 0 보다 큰 경우 시계 방향
- 0 보다 작은 경우 반시계 방향
- 0인 경우 평행
로 판단한다.
만약 점 A, B, C가 반시계 방향이고, 점 A, B, D가 시계 방향 이라면 서로 교차한다.
만약 점 A, B, C 가 반시계 방향이고, 점 A, B, D 가 반시계 방향이라면 서로 교차하지 않는다.
즉, 각 점들을 CCW한 값의 곱이 음수라면 교차하고, 양수라면 교차하지 않는다.
단, 좌표 평면상에서는 CCW 곱의 값이 음수인 경우가 존재하지만 교차하지 않는 경우가 발생할 수 있다.
그러므로 좌표 평면 상에서 교차 여부를 알기 위해서, 점 A, B, C, D를 모두 검사한다.
CCW(A, B, C) * CCW(A, B, D) 도 음수이고, CCW(C, D, A) * CCW(C, D, B) 도 음수인 경우를 찾아야한다.
단, 모든 점이 평행할 때 교차 여부를 판단하려면 점 A, B를, 점 C, D를 작은 점에서 출발 할 수 있도록 상대 위치를 변경해준다.
그리고 해당 문제에서 요구하는 교차하는 선분의 집합과 해당 집합 속 선분의 개수를 알기 위해서, 유니온 파인드 알고리즘으로 집합을 구하고 같은 집합에 속한 선분을 구한다.
유의할 점은 교차하는 중 유니온 파인드를 수행하고 마지막으로 한번 더 유니온 파인드를 수행하여 집합을 압축시킨다.
코드
from sys import stdin
from collections import Counter
input = stdin.readline
N = int(input())
def find(A, root):
if A == root[A]:
return A
else:
root[A] = find(root[A], root)
return root[A]
def union(A, B, root):
A = find(A, root)
B = find(B, root)
if A < B:
root[B] = A
else:
root[A] = B
def CCW(P1, P2, P3):
x1, y1 = P1
x2, y2 = P2
x3, y3 = P3
S = (x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1)
if S > 0:
return 1
elif S < 0:
return -1
else:
return 0
points = []
root = [i for i in range(N)]
for _ in range(N):
x1, y1, x2, y2 = map(int, input().split())
points.append([(x1, y1), (x2, y2)])
for i in range(N):
A, B = points[i]
for j in range(N):
if i == j:
continue
cross = False
C, D = points[j]
ABC = CCW(A, B, C)
ABD = CCW(A, B, D)
CDA = CCW(C, D, A)
CDB = CCW(C, D, B)
if ABC * ABD <= 0 and CDA * CDB <= 0:
if ABC * ABD == 0 and CDA * CDB == 0:
if A > B:
temp = B
B = A
A = temp
if C > D:
temp = C
C = D
D = temp
if C <= B and A <= D:
cross = True
else:
cross = True
if cross:
union(i, j, root)
for i in range(N):
root[i] = find(i, root)
counter = Counter(root)
print(len(counter))
print(counter.most_common()[0][1])
