[BOJ 10839] 미술관

문제

---

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

풀이

---

최단거리는 볼록 껍질을 만드는 로직을 반대로 이용하면 된다.

즉 CCW가 음수일 때만 꼭짓점을 경로에 넣는 것이다.

주의할 점은, $ \overline {v_0v_1} $를 훑으면 안 된다.

예로 들어, 시작점, 도착점이 각각 $ v_i, v_j (i > j)$로 주어졌을 때 $ v_i, v_{i + 1}, …, v_{j - 1}, v_j $처럼 훑으면 안 되고, 뒤집어서 $ v_j, v_{j + 1}, …, v_{i - 1}, v_i $를 훑어야 한다.

우선 전자의 방법대로 해보자.

문제의 조건에 따라 $ \overline {v_i v_0} $ 또는 $ \overline {v_i v_1} $이 P의 외부와 만나지 않는다.

마찬가지로 $ \overline {v_0 v_j} $ 또는 $ \overline {v_1 v_j} $이 P의 외부와 만나지 않는다.

그러므로 위 최단거리 알고리즘을 적용하면 $ v_i $와 $ v_j $ 사이의 최단거리는 그 둘을 일직선으로 이은 거리가 된다는 모순이 생긴다.

그럼 왜 후자의 방법은 유효할까?

최단거리라는 것은, 경로의 일부라도 P의 외부에 없으면서 더 짧은 경로 또한 존재하지 않는 것이다.

그러므로 모순이 발생하려면, $ v_j, v_{j + 1}, …, v_{i - 1}, v_i $ 외의 꼭짓점이 두 번째 방법으로 구한 $ v_j $부터 $ v_i $의 최단거리 경로를 침범해야 한다. (최단거리 경로의 일부를 P 외부에 있도록 해야 한다.)

엄밀하진 않지만 이 경우엔 $ v_0, v_1 $ 둘 모두로부터 조명을 받지 못하게 된다.

코드

---

import sys


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


n = int(sys.stdin.readline())
coord = [tuple(map(int, sys.stdin.readline().split())) for _ in range(n)]
start, end = map(int, sys.stdin.readline().split())

if (start - end) % n in [1, n - 1]:
    print(2)
    print(start, end)
    exit()

flag = 0
if (start == 0) or (end != 0 and start > end):
    flag = 1
    start, end = end, start

stack = [start, (start + 1) % n]

for i in range(start + 2, start + n):
    i %= n
    while len(stack) >= 2:
        if ccw(*coord[stack[-2]], *coord[stack[-1]], *coord[i]) >= 0:
            stack.pop()
        else:
            break
    
    stack.append(i)
    if i == end:
        break

if flag:
    stack.reverse()

print(len(stack))
print(*stack)

‘최단 경로 상의 꺾인 점’만 출력하라고 되어있기 때문에, 최단 경로에 놓인 연속한 세 개 이상의 꼭짓점이 일직선이 되는 경우 양쪽 끝 꼭짓점만 정답에 포함시켜야 한다.