[백준] 2166 다각형의 면적 (Python)

 

문제

 

문제

2차원 평면상에 N(3 ≤ N ≤ 10,000)개의 점으로 이루어진 다각형이 있다. 이 다각형의 면적을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. 다음 N개의 줄에는 다각형을 이루는 순서대로 N개의 점의 x, y좌표가 주어진다. 좌표값은 절댓값이 100,000을 넘지 않는 정수이다.

출력

첫째 줄에 면적을 출력한다. 면적을 출력할 때에는 소수점 아래 둘째 자리에서 반올림하여 첫째 자리까지 출력한다.

예제 입력 1 복사

4
0 0
0 10
10 10
10 0

예제 출력 1 복사

100.0

 

---

문제 풀이

 

 

다각형을 이루는 점들을 중심점과 이어 삼각형을 만들고, 그 삼각형의 크기들을 합하여 결과를 도출하려 했었다.

 

틀린 코드

def triangle(dot1,dot2,dot3):
    #길이 구하기
    a = ((dot1[0]-dot2[0])**2 + (dot1[1]-dot2[1])**2)**0.5
    b = ((dot2[0]-dot3[0])**2 + (dot2[1]-dot3[1])**2)**0.5
    c = ((dot3[0]-dot1[0])**2 + (dot3[1]-dot1[1])**2)**0.5
    # print(a,b,c)
    if not a or not b or not c:
        return 0
    #코사인 값 구하기 (코사인 제 2법칙)
    cos = (a**2+b**2-c**2)/(2*a*b)
    #사인 값 구하기 (cos**2 + sin**2 == 1)
    sin = (1-cos**2)**0.5
    #높이 구하기
    h = sin*a
    #결과 반환
    return 1/2*b*h

N = int(input())
dots = [list(map(int,input().split())) for _ in range(N)]
middle = [sum([i[0] for i in dots])/N,sum([i[1] for i in dots])/N]
# 중심점
dots.append(dots[0])

answer = 0
for i in range(N):
    a = dots[i]
    b = dots[i+1]
    c = middle
    
    answer += triangle(a,b,c)
    
print(round(answer,2))

 

하지만 선분이 어떤 한 점을 기준으로 겹칠수도 있다는 사실을 간과하였다.

 

대부분의 수학 문제가 그렇듯

이 문제는 "신발끈 공식" 을 알지 못하면 해결할 수 없는 어찌 보면 불합리한 문제이다.

 

신발끈 공식의 정의는 다음과 같다.

신발끈 공식 - 위키백과, 우리 모두의 백과사전

 

이 공식을 사용하면 문제를 쉽게 풀 수 있다.

---

코드

 

N = int(input())
dots = [list(map(int,input().split()))for _ in range(N)]
dots.append(dots[0])
answer = 0
for i in range(N):
    answer+= dots[i][0] * dots[i+1][1]
    answer -= dots[i+1][0] * dots[i][1]
print(round(abs(answer/2),2))

---