드디어 볼록 껍질 알고리즘을 제대로 공부하기 시작했다.
CCW 개념을 아니깐 바로 이해가 간다.
이참에 볼록 껍질의 최대 직경을 재는 회전하는 캘리퍼스까지 얹어서 진행시켜!

BOJ 9240 - 로버트 후드 링크
(2022.09.29 기준 P3)
(치팅한 사람 계정 차단 진행시켜)

문제

과녁에 적중된 C개의 화살의 좌표가 주어질 때, 가장 먼 화살의 거리

알고리즘

화살들의 볼록 껍질을 구해, 볼록 껍질의 최대 직경을 회전하는 캘리퍼스를 이용해 구해야 한다.

풀이

전형적인 회전하는 캘리퍼스 문제.
가장 먼 화살의 거리를 구해야 하므로, 볼록 껍질의 최대 직경을 구하면 된다.

일단 볼록 껍질부터 구하자.
파이썬에선 monotone chain 알고리즘을 사용해 볼록 껍질을 구하는 것이 편하다.
다른 언어는 그라함 스캔으로 구해도 무방.
단, 제일 중요한 것은 볼록 껍질이 시계 방향이든 반시계 방향이든 꼭 정렬되어 있어야 한다.
왜냐면, 회전하는 캘리퍼스 자체가 한 방향으로 회전시키면서 볼록 껍질의 직경을 구할 것이기 때문이다.
난 일단 반시계 방향으로 정렬했다.

그 다음은 회전하는 캘리퍼스
진짜 이해가 잘 가지 않는 알고리즘이다. 대충 요약하자면,
직경을 재는 도구인 캘리퍼스로 직경을 재고자 하는 다각형에 직접 대고 회전시키면서 직경을 측정하는 방식을 구현한 알고리즘이다. 양 끝점을 먼저 잡아 직경을 재고, 각 점의 다음 방향의 점과의 각도가 작은 곳으로 이동하면서 직경을 재나가면 된다.
이 블로그에 정말 잘 설명되어 있으니 참고하자.

이 문제는 볼록 껍질과 회전하는 캘리퍼스. 두 알고리즘이 담겨 있는 문제인데, 정말 알고리즘만 알면 풀린다. 즉, 응용할 필요가 없는 문제이다. 코드에 주석을 달아놓았으니, 코드를 보면서 알고리즘을 익혀보자.

코드

import sys; input = sys.stdin.readline

def ccw(a, b, c): # a-b-c가 반시계 방향인지 검사
    if (a[0] * b[1] + b[0] * c[1] + c[0] * a[1]) - (a[1] * b[0] + b[1] * c[0] + c[1] * a[0]) > 0:
        return True
    return False

def dist(a, b): # a-b 거리 계산 (제곱 형태로 반환)
    return (a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2

def solve():
    C = int(input())
    if C == 2: # 화살이 2개면 거리 계산하여 출력 후 프로그램 종료
        a = list(map(int, input().split()))
        b = list(map(int, input().split()))
        print(dist(a, b) ** 0.5)
        return
    
    # 화살이 3개 이상이면 먼저 볼록 껍질을 구해야 한다.
    # monotone chain 알고리즘을 사용해서 구할 것이므로
    # 먼저 화살들이 x, y가 오름차순이 되게 정렬하자.
    arrows = sorted(list(map(int, input().split())) for _ in range(C))
    # 볼록 껍질의 아래
    convex_hull_down = []
    for i in range(C):
        while len(convex_hull_down) > 1:
            if ccw(convex_hull_down[-2], convex_hull_down[-1], arrows[i]):
                break
            convex_hull_down.pop()
        convex_hull_down.append(arrows[i])
    # 정렬된 반대로 탐색하여 볼록 껍질의 위를 구한다.
    convex_hull_up = []
    for i in range(C - 1, -1, -1):
        while len(convex_hull_up) > 1:
            if ccw(convex_hull_up[-2], convex_hull_up[-1], arrows[i]):
                break
            convex_hull_up.pop()
        convex_hull_up.append(arrows[i])
    # 두 볼록 껍질의 양 끝은 겹치기 때문에 겹치는 부분은 제외해서 합치자.
    # 겹치는 부분은 양 끝점이므로 회전하는 캘리퍼스의 시작점이 된다.
    lp, rp = 0, len(convex_hull_down) - 1
    convex_hull = convex_hull_down[:-1] + convex_hull_up[:-1] # 반시계 방향이 되게끔

    # 회전하는 캘리퍼스
    # 초기 답은 lp와 rp의 거리로 저장해두고 시작
    answer = dist(convex_hull[lp], convex_hull[rp])
    size = len(convex_hull) # 볼록 껍질의 크기
    for _ in range(size):
        lx, ly = convex_hull[lp]
        llx, lly = convex_hull[(lp + 1) % size]
        rx, ry = convex_hull[rp]
        rrx, rry = convex_hull[(rp + 1) % size]
        # 양 끝점과 그 점들의 반시계 방향의 다음 점과 벡터를 잡고
        # 두 벡터가 CCW이면 lp를 반시계 방향으로 한칸 이동
        # CW이면 rp를 반시계 방향으로 한칸 이동
        # 이를 볼록 껍질의 개수만큼 반복하면 된다.
        if ccw([llx - lx, lly - ly], [0, 0], [rrx - rx, rry - ry]):
            lp = (lp + 1) % size
        else:
            rp = (rp + 1) % size
        answer = max(answer, dist(convex_hull[lp], convex_hull[rp])) # 돌릴 때마다 거리 갱신
    print(answer ** 0.5) # 답 출력

solve()

여담

볼록 껍질은 꽤 빨리 깨달았는데, 회전하는 캘리퍼스는 아직 연습이 많이 필요한 것 같다. 원리는 이해가 가는데.. 알고리즘 자체가 내 머리속에 달라붙질 않네..