import sys
input = sys.stdin.readline
def findparent(x):
if parent[x] == x:
return x
parent[x] = findparent(parent[x])
return parent[x]
def eq(x,y,i):
return (x2[i]-x1[i])*(y-y1[i])-(y2[i]-y1[i])*(x-x1[i])
def check(i,j):
if eq(x1[j],y1[j],i)*eq(x2[j],y2[j],i)<=0 and eq(x1[i],y1[i],j)*eq(x2[i],y2[i],j)<=0:
if x2[i]-x1[i] == x2[j]-x2[j] == 0:
if max(y1[i],y2[i])>=min(y1[j],y2[j]) and max(y1[j],y2[j])>=min(y1[i],y2[i]):
return 1
elif (y2[j]-y1[j])*(x2[i]-x1[i]) == (y2[i]-y1[i])*(x2[j]-x1[j]):
if y1[i]-(y2[i]-y1[i])/(x2[i]-x1[i])*x1[i] == y1[j]-(y2[j]-y1[j])/(x2[j]-x1[j])*x1[j]:
if max(x1[i],x2[i])>=min(x1[j],x2[j]) and max(x1[j],x2[j])>=min(x1[i],x2[i]):
return 1
else:
return 1
return 0
N = int(input())
x1,y1,x2,y2 = [0]*N,[0]*N,[0]*N,[0]*N
for i in range(N):
x1[i],y1[i],x2[i],y2[i] = map(int,input().split())
parent = {i:i for i in range(N)}
for i in range(N):
for j in range(N):
if findparent(i) != findparent(j):
if check(i,j):
if parent[i] < parent[j]:
parent[parent[j]] = parent[i]
else:
parent[parent[i]] = parent[j]
cnt = 0
parentcnt = [0]*N
for i in range(N):
x = findparent(i)
if parentcnt[x] == 0:
cnt += 1
parentcnt[x] += 1
print(cnt)
print(max(parentcnt))
선분교차2를 약간 응용한 문제이다.
알고리즘 자체는 선분교차2와 똑같다. 거기에 union-find만 살짝 결합시켜주면 된다.
선분그룹2의 선분교차 판별을 함수로 지정하고 이중 for문을 돌면서 두 선분이 교차한다면 같은 그룹에 union 시켜주면 된다.
두개의 알고리즘을 잘 버무린 재밌는 문제였다.
오늘의 교훈) union-find 알고리즘을 잘 활용하자