import sys
sys.setrecursionlimit(10**4)
input = lambda : [*map(int,sys.stdin.readline().split())]
def ccw(x1,y1,x2,y2,x,y):
return (x2-x1)*(y-y1)-(y2-y1)*(x-x1)
def crossed(x1,y1,x2,y2,x3,y3,x4,y4):
return 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
def DFS(now):
global id
ID[now] = nowid = id
stack.append(now)
for next in graph[now]:
if scc[next]:
continue
if not ID[next]:
id += 1
DFS(next)
ID[now] = min(ID[now],ID[next])
if ID[now]==nowid:
SCC.append([])
while 1:
x = stack.pop()
scc[x] = len(SCC); SCC[-1].append(x)
if x==now:
return
def dfs(now):
visited[now] = 1; visited[(now+3*N)%(6*N)] = -1
for next in graph[now]:
if not visited[next]:
dfs(next)
[N] = input()
stick = [input() for i in range(3*N)]
graph = [[] for i in range(6*N)]
for i in range(N):
for j in [0,1,2]:
for k in [1,2]:
graph[i*3+j+3*N].append(i*3+(j+k)%3)
for i in range(3*N):
for j in range(i+1,3*N):
if crossed(*stick[i],*stick[j]):
graph[i].append(j+3*N); graph[j].append(i+3*N)
stack = []; scc = [0]*6*N; SCC = []
ID = [0]*6*N
for i in range(3*N):
if not ID[i]:
id = 1
DFS(i)
if sum(scc[i]==scc[i+3*N] for i in range(3*N)):
print(-1)
else:
SCC.reverse(); visited = [0]*6*N
for S in SCC:
for i in S:
if not visited[i]:
dfs((i+3*N)%(6*N))
print(sum(visited[i]<0 for i in range(3*N)))
for i in range(3*N):
if visited[i]<0:
print(i+1,end=" ")
2-SAT 응용문제
TV Show Game [백준 16367번] TV Show Game (Python3) (tistory.com) 을 약간 업그레이드 시킨 문제이다.
풀이를 설명하면,
1. 막대기를 남기는 경우를 True, 남기지 않는 경우를 False로 둔다.
2. 각 학생의 세 개의 막대가 있을 때, 2개 이상이 참이어야 한다. 예를들어 막대를 x,y,z로 두면 x가 거짓이면 y와 z가 참이어야 한다. 이를 간선으로 나타낸다. ( = TV Show Game)
3. 선분교차 ( = [백준 17386번] 선분 교차 1 (Python3) (tistory.com) ) 한 막대가 있는 경우 두 막대 중 한 막대만이 참이어야 한다. 예를들어 막대 x,y가 교차하고 있으면 x가 참이면 y가 거짓이어야 한다. 이를 간선으로 나타낸다.
4. 이외 풀이 방식은 2-SAT 알고리즘을 이용한다. ( = [백준 11281번] 2-SAT - 4 (Python3) (tistory.com) )
아이디어가 비슷하기에 2-sat라는 사실을 알고 TV Show Game 문제를 풀고나면 쉽게 해결할 수 있는 문제이다. 하지만 2-sat라는 사실을 모른 채로 풀면 꽤나 애먹었을 것 같다.
오늘의 교훈) 2-sat로 해결할 수 있는지 잘 관찰하자