백준 - 선분 그룹(2162) 본문
올해 푼 문제 중에 가장 어려웠다.
수학적 지식이 필요한 문제인지라
과거 공부에 뜻이 없었던 나에게 상당히 어려웠다.
이 문제의 핵심은 ccw 알고리즘이다.
벡터의 외적을 이용해서 선분이 교차하는지 판단할 수 있다.
게임에서도 ccw 알고리즘이 많이 쓰인다고 한다.
위치 판별 및 물체 부딪힘 등등
신기하다....
선분 (A, B), (C, D)가 있을 경우
CCW(A, B, C)*CCW(A, B, D) < 0 and CCW(C, D, A)*CCW(C, D, A) < 0
가 둘다 -1이 나올 경우 접점이다.
예외는
둘다 일직선 상으로 겹치는 경우이다.
둘 다 0일 경우 좌표 위치를 계산해서 겹치는지 판단한다.
그리고 그룹을 구해야 하기 때문에 union find를 사용했다.
from collections import Counter
def ccw(x1,x2,x3,y1,y2,y3):
v = x1 * y2 + x2 * y3 + x3 * y1 - x2 * y1 - x3 * y2 - x1 * y3
if v > 0:
return 1
elif v<0:
return -1
else:
return 0
def ccw_cal(x1,y1,x2,y2,x3,y3,x4,y4):
a = ccw(x1,x2,x3,y1,y2,y3)*ccw(x1,x2,x4,y1,y2,y4)
b = ccw(x3,x4,x1,y3,y4,y1)*ccw(x3,x4,x2,y3,y4,y2)
if a == 0 and b == 0:
if min(x1,x2) <= max(x3,x4) and max(x1,x2) >= min(x3,x4) and min(y1,y2) <= max(y3,y4) and max(y1,y2) >= min(y3,y4):
return True
elif a <= 0 and b <= 0:
return True
return False
def find(v):
if parent[v] == v:
return v
parent[v] = find(parent[v])
return parent[v]
def union(i,j):
a = find(i)
b = find(j)
if a == b:
return
if a < b:
parent[b] = a
else:
parent[a] = b
data = []
n = int(input())
lines = [list(map(int, input().split())) for _ in range(n)]
parent = [i for i in range(n)]
for i in range(n):
for j in range(i+1,n):
x1,y1,x2,y2 = lines[i]
x3,y3,x4,y4 = lines[j]
if ccw_cal(x1, y1, x2, y2, x3, y3, x4, y4):
union(i,j)
for i in range(n):
parent[i] = find(i)
answer = Counter(parent).most_common()
print(len(answer))
print(answer[0][1])
'알고리즘' 카테고리의 다른 글
백준 - 멀티탭 스케줄링(1700) (0) | 2023.12.12 |
---|---|
백준 - 가장 긴 증가하는 부분 수열5(14003) (0) | 2023.12.12 |
백준 - 롤러코스터(2873) (1) | 2023.12.12 |
백준 - 여러분의 다리가 되어 드리겠습니다!(17352) (1) | 2023.12.10 |
백준 - 라면사기(18185) (0) | 2023.12.09 |
Comments