[BOJ 2519] 막대기

문제

---

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

풀이

---

파이프 청소와 매우 유사하다.

추가된 것이라곤 각 학생별로 세 막대 중 하나만 제거할 수 있는 점이다.

이는 6개의 간선을 추가함으로써 해결된다.

코드

---

import sys
sys.setrecursionlimit(10 ** 5)


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


def intersect(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)

    return (res1 * res2 < 0) and (res3 * res4 < 0)


n = int(sys.stdin.readline())
stick = [tuple(map(int, sys.stdin.readline().split())) for _ in range(3 * n)]
graph = [[] for _ in range(6 * n + 1)]

for i in range(n):
    graph[3 * i + 1].append(-3 * i - 2)
    graph[3 * i + 1].append(-3 * i - 3)
    graph[3 * i + 2].append(-3 * i - 3)
    graph[3 * i + 2].append(-3 * i - 1)
    graph[3 * i + 3].append(-3 * i - 1)
    graph[3 * i + 3].append(-3 * i - 2)

for i in range(1, 3 * n + 1):
    for j in range(1, i):
        if intersect(*stick[i - 1], *stick[j - 1]):
            graph[-i].append(j)
            graph[-j].append(i)

stack = []
scc_num = 1
scc_idx = [0] * (6 * n + 1)
finish = [0] * (6 * n + 1)
visit = [0] * (6 * n + 1)
idx = 1


def dfs(cur):
    global idx, scc_num
    visit[cur] = idx
    low = idx
    idx += 1
    stack.append(cur)

    for nxt in graph[cur]:
        if not visit[nxt]:
            low = min(low, dfs(nxt))
        elif not finish[nxt]:
            low = min(low, visit[nxt])

    if low == visit[cur]:
        while stack:
            top = stack.pop()
            finish[top] = 1
            scc_idx[top] = scc_num
            if cur == top:
                break

        scc_num += 1

    return low


for i in range(1, 6 * n + 1):
    if not visit[i]:
        dfs(i)

res = [0] * (3 * n)
for i in range(1, 3 * n + 1):
    if scc_idx[i] == scc_idx[-i]:
        print(-1)
        break
    if scc_idx[i] < scc_idx[-i]:
        res[i - 1] = 1
else:
    print(res.count(1))
    for i in range(3 * n):
        if res[i]:
            print(i + 1, end=' ')