이 블로그를 보고 풀었다.
그런데, 왜 $2\pi l$을 하면 답이 나오는지 명확한 설명이 되어있지 않아서, 간단한 증명을 해봤다.
솔직히 증명이 어려울줄 알았는데, 생각보다 매우 간단해서 다행이다.
$n$각형에 대해, 내각을 $A_1, A_2, A_3, \dots A_n$이라 하고, 자연수 $k$에 대하여 $A_k$와 마주보는 굽어지는 각(곡선으로 둘러싸이는 부분)을 $B_k$라 하자.
이때, $$\sum_{i=1}^{n}{B_i} = 180n - \sum_{i=1}^{n}{A_i}$$
$n$각형의 내각의 합은 $180(n-2)$이므로, 앞의 식은 $180n - 180(n-2) = 360. \ \blacksquare$
따라서, 항상 굽어지는 각의 합은 360. 따라서 $2\pi l$을 해도 답이 나옴.
굽어지는 각이라고 말하고 설명하는게 마음에 들지는 않는다. 그래도 뭐라 말해야 될지를 모르겠어서 이렇게 적었다.
뭐 가장 중요한것은 n각형의 내각의 합 공식이다.
다음은 코드다.
import sys
import math
input = sys.stdin.readline
def round(n):
return int((n*10 + 5)/10)
def ccw(p1, p2, p3):
return p1[0]*(p2[1] - p3[1]) + p2[0]*(p3[1] - p1[1]) + p3[0]*(p1[1] - p2[1])
def monotonechain(dots):
dots.sort()
if len(dots) <=1:
return dots
lower = []
for d in dots:
while len(lower) >= 2 and ccw(lower[-2], lower[-1], d) <= 0:
lower.pop()
lower.append(d)
upper = []
for d in reversed(dots):
while len(upper) >= 2 and ccw(upper[-2], upper[-1], d) <= 0:
upper.pop()
upper.append(d)
return lower[:-1] + upper[:-1]
def getDist(p1,p2):
return math.sqrt((p1[0] - p2[0])**2 + (p1[1] - p2[1])**2)
n,l = map(int, input().split())
buildings = [[int(i) for i in input().split()] for _ in range(n)]
convexHull = monotonechain(buildings)
s = 0
for i in range(len(convexHull)):
s += getDist(convexHull[i-1], convexHull[i])
s += 2*math.pi*l
print(round(s))
얘는 코드 복붙으로 해결된다.(반올림만 바꿔주면 됨)
처음엔 문제 이해가 잘 안됐는데, 7420번의 난이도 기여에서 이문제와 같다는 걸 보고서야 뭔말인지 이해했다.
'알고리즘 > BOJ' 카테고리의 다른 글
14502-연구소 (0) | 2021.05.19 |
---|---|
17978-Washer (2) | 2020.12.25 |
15682 - 삼차 방정식 풀기 2 (0) | 2020.12.25 |
13705-Ax+Bsin(x)=C (0) | 2020.12.25 |
[Python]10254-고속도로 (2) | 2020.09.12 |
[Python]4181-Convex Hull (0) | 2020.09.12 |
[C++]11930-Smallest Enclosing Sphere (0) | 2020.09.12 |
[Python]2389-세상의 중심에서... (0) | 2020.09.12 |