[BOJ 11668] 파이프 청소

문제

---

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

풀이

---

두 파이프가 교차한다면 둘 중 하나엔 꼭 로봇을 보내야 한다.

사실 선분 교차 판정 + disjoint set만으로도 풀 수 있다.

코드

---

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(s, x2, y2, t, x4, y4):
    x1, y1 = water[s - 1]
    x3, y3 = water[t - 1]

    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)

    if res1 == res2 == res3 == res4 == 0:
        if (max(x1, x2) < min(x3, x4)) or (max(x3, x4) < min(x1, x2)) or (max(y1, y2) < min(y3, y4)) or (max(y3, y4) < min(y1, y2)):
            return 0
        else:
            return 1
    elif (res1 * res2 <= 0) and (res3 * res4 <= 0):
        return 1
    else:
        return 0


w, p = map(int, sys.stdin.readline().split())
water = [tuple(map(int, sys.stdin.readline().split())) for _ in range(w)]
graph = [[] for _ in range(2 * p + 1)]
pipe = []

for _ in range(p):
    s, x, y = map(int, sys.stdin.readline().split())
    pipe.append((s, x, y))
    for i in range(1, len(pipe)):
        if (s != pipe[i - 1][0]) and intersect(s, x, y, *pipe[i - 1]):
            graph[i].append(-len(pipe))
            graph[len(pipe)].append(-i)
            graph[-i].append(len(pipe))
            graph[-len(pipe)].append(i)

stack = []
scc_num = 1
scc_idx = [0] * (2 * p + 1)
finish = [0] * (2 * p + 1)
visit = [0] * (2 * p + 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, 2 * p + 1):
    if not visit[i]:
        dfs(i)

for i in range(1, p + 1):
    if scc_idx[i] == scc_idx[-i]:
        print('impossible')
        break
else:
    print('possible')