[BOJ 7420] 맹독 방벽

문제

---

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

풀이

---

방벽이 어떻게 생겼는지 상상해보면, 곡선 부분을 다 합쳤을 때 정확하게 원이 나오는 것을 알 수 있다.

나머지 부분의 길이의 합은 볼록 껍질의 둘레의 길이와 같다.

코드

---

import sys
from math import pi


def tangent(x, y):
    if x == a:
        return 1, y
    if x > a:
        return 0, (y - b) / (x - a), x
    if x < a:
        return 2, (y - b) / (x - a), x


def isline(x, y, z):
    return (y[1] - x[1]) * (z[0] - y[0]) == (z[1] - y[1]) * (y[0] - x[0])


n, l = map(int, sys.stdin.readline().split())

coord = [tuple(map(int, sys.stdin.readline().split())) for _ in range(n)]
coord.sort(key=lambda x: (x[1], x[0]))
a, b = coord.pop(0)

coord.sort(key=lambda x: tangent(x[0], x[1]))
stack = [(a, b), coord[0]]
idx = 0

while idx < n - 2:
    idx += 1
    w1, w2 = coord[idx]
    while len(stack) >= 2:
        u1, u2 = stack[-2]
        v1, v2 = stack[-1]
        if (v1 - u1) * (w2 - v2) <= (v2 - u2) * (w1 - v1):
            stack.pop()
        else:
            break
    
    stack.append((w1, w2))
    if (len(stack) >= 3) and isline(stack[-3], stack[-2], stack[-1]):
        stack.pop(-2)

if (len(stack) >= 3) and isline(stack[-2], stack[-1], stack[0]):
        stack.pop()

res = 2 * pi * l
for i in range(-1, len(stack) - 1):
    res += ((stack[i][0] - stack[i + 1][0]) ** 2 + (stack[i][1] - stack[i + 1][1]) ** 2) ** 0.5

print(round(res))