다각형의 외곽 꼭짓점들이 시계 방향 순서로 주어져 있다고 가정해 보겠습니다. 이 점들이 볼록 다각형(convex polygon)을 이루는지, 아니면 오목 다각형(concave polygon)을 이루는지 판별해야 합니다. 다각형의 내각 중 하나라도 180°보다 크면 그 다각형은 오목 다각형으로 정의됩니다.
위 그림에서 알 수 있듯이, 연속된 세 개의 꼭짓점이 이루는 내각은 CDE 구간을 제외하면 모두 180° 이하입니다. 즉, 어느 한 지점에서라도 내각이 180°를 초과하면 해당 다각형은 오목하다고 판단할 수 있습니다.
예를 들어 입력이 points = [(3,4), (4,7), (7,8), (8,4), (12,3), (10,1), (5,2)]와 같다면 출력은 True가 됩니다.
문제 해결 접근 방법
이 문제는 다음과 같은 단계로 해결할 수 있습니다.
- n := 점(points)의 개수
- i를 0부터 점의 개수까지 반복합니다.
- p1 := i > 1이면 points[i-2], 그렇지 않으면 points[n-2]
- p2 := i > 0이면 points[i-1], 그렇지 않으면 points[n-1]
- p3 := points[i]
- 세 점 (p1, p2, p3)이 이루는 각도가 180°보다 크면 True를 반환합니다.
- 반복이 끝날 때까지 조건에 해당하지 않으면 False를 반환합니다.
여기서 각도는 math.atan2() 함수를 사용하여 두 벡터 사이의 각도를 계산합니다. 계산 결과가 음수일 경우 360°를 더해 0~360° 범위로 정규화함으로써, 내각이 180°를 초과하는지 정확하게 비교할 수 있습니다.
예제 코드
아래 구현 예제를 통해 더 쉽게 이해해 보겠습니다.
import math
def get_angle(a, b, c):
angle = math.degrees(math.atan2(c[1]-b[1], c[0]-b[0]) - math.atan2(a[1]-b[1], a[0]-b[0]))
return angle + 360 if angle < 0 else angle
def solve(points):
n = len(points)
for i in range(len(points)):
p1 = points[i-2]
p2 = points[i-1]
p3 = points[i]
if get_angle(p1, p2, p3) > 180:
return True
return False
points = [(3,4), (4,7),(7,8),(8,4),(12,3),(10,1),(5,2)]
print(solve(points))
입력
[(3,4), (4,7),(7,8),(8,4),(12,3),(10,1),(5,2)]
출력
True