[Python]7420-맹독 방벽

www.acmicpc.net/problem/7420

7420번: 맹독 방벽

manoflearning.tistory.com/216

백준 7420번: 맹독 방벽

이 블로그를 보고 풀었다.

그런데, 왜 $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))

www.acmicpc.net/problem/10903

10903번: Wall construction

얘는 코드 복붙으로 해결된다.(반올림만 바꿔주면 됨)

처음엔 문제 이해가 잘 안됐는데, 7420번의 난이도 기여에서 이문제와 같다는 걸 보고서야 뭔말인지 이해했다.