볼록 다각형의 성질을 알아야 하는 문제가 있다.
바로 이 문제.

BOJ 7420 - 맹독 방벽 링크
(2022.09.29 기준 P5)
(치팅하면 맹독 방벽에 닿음)

문제

모든 건물로부터 L 이상의 거리를 두는 방벽의 최소 길이

알고리즘

모든 건물의 볼록 껍질을 구하여 방벽의 둘레를 구해야 한다.

풀이

볼록 껍질을 구해야 한다는 것은 당연하니 일단 구하자.

이제 문제는 방벽의 둘레. 직선이 되지 않는 이상 꼭짓점을 두르는 방벽은 둥근 모양이 된다.

이런 식으로 방벽이 둘러질 텐데, 이 둘레를 어떻게 구해야 하냐.
방벽은 사실 볼록 다각형의 선분이 L만큼 평행하게 멀어져 있고 그 선분들을 부채꼴 모양으로 이어지는 형태다. 밑 그림을 보면
(나 그림 못그림)
이렇게 선분들이 평행하게 멀어져 있고 떨어져 있는 선분들을 부채꼴 형태로 이어지는 형태를 확인할 수 있는데, 이 부채꼴들의 각의 합은 360도이다.
증명은 못하겠지만 직관적으로 봐도 알 수 있는데, 이는 볼록 다각형이면 전부 해당한다고 한다. 그러므로 건물들의 볼록 껍질을 구하고, 그 볼록 껍질의 둘레와 L이 반지름이 되는 원의 둘레를 합치면 방벽의 둘레가 된다.

코드

import sys; input = sys.stdin.readline
from math import pi

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():
    N, L = map(int, input().split())
    # 건물들의 좌표가 x, y 오름차순이 되게 정렬한다.
    buildings = sorted(list(map(int, input().split())) for _ in range(N))

    # monotone chain
    # 볼록 껍질의 아래
    convex_hull_down = []
    for i in range(N):
        while len(convex_hull_down) > 1:
            if ccw(convex_hull_down[-2], convex_hull_down[-1], buildings[i]):
                break
            convex_hull_down.pop()
        convex_hull_down.append(buildings[i])
    # 볼록 껍질의 위
    convex_hull_up = []
    for i in range(N - 1, -1, -1):
        while len(convex_hull_up) > 1:
            if ccw(convex_hull_up[-2], convex_hull_up[-1], buildings[i]):
                break
            convex_hull_up.pop()
        convex_hull_up.append(buildings[i])
    # 볼록 껍질의 아래와 위를 합치자.
    # 양 끝점이 겹치는데, 모든 선분의 길이를 확인해야 하므로 시작점은 끝에 한번 더 넣자.
    convex_hull = convex_hull_down[:-1] + convex_hull_up
    # 볼록 껍질의 각 선분의 길이의 합과 반지름 L인 원의 둘레를 합하여 출력
    print(format(sum(dist(convex_hull[i], convex_hull[i + 1]) ** 0.5 for i in range(len(convex_hull) - 1)) + 2 * pi * L, '.0f'))

solve()

여담

지금 볼록 껍질 문제에 빠져 있다. 꽤 재밌는 알고리즘인 듯?
그런데 여기에만 집중하니깐 다른 알고리즘이 잘 생각이 나지 않는다.. ㅋㅋㅋㅋㅋㅋ
다양한 알고리즘을 풀어야 할 듯