[BOJ/Python] 2166_다각형의 면적

문제 출처:https://www.acmicpc.net/problem/2166

2166번: 다각형의 면적

 

문제

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

 

---

풀이

 

다각형의 면적을 구하기 위해 벡터의 외적을 이용하였다. 두 벡터의 외적의 크기는 평행사변형의 넓이와 같다는 성질을 이용하였다. 아래는 이 게시물을 읽기 전에 참고하면 좋은 게시물이다.

 

CCW(counter clockwise) 알고리즘

 

우선 오각형의 넓이를 구하는 과정을 살펴보자면 다음과 같다.

 

벡터의 외적의 크기 = 평행사변형의 넓이

 

벡터의 외적의 크기는 두 벡터가 만드는 평행사변형의 넓이와 같음을 이용한다.

위 그림에서 알 수 있듯이, 평행사변형의 넓이를 2로 나누게 되면 삼각형 면적 S1을 구할 수 있다.

위 과정을 반복하면 오각형의 넓이를 S1 + S2 + S3 임을 알 수 있다.

 

하지만, 다음과 같이 면적을 구해야 하는 도형에 오목한 부분이 있다면 조금 더 생각해봐야 한다.

 

 

왼쪽 도형의 경우, 오각형의 면적을 구한 방법 그대로 구할 수 있지만, 오른쪽 도형의 경우 면적을 구할 때 주의해야 할 부분이 있다. 

어째서 왼쪽과 오른쪽 도형이 다른 결과가 나오는지에 대한 생각이 필요하다. 결론부터 말하자면, 점들의 방향관계문제이다.

 

이 도형을 먼저 살펴보자면, 점들을 같은 방향으로 순차적으로 접근하여 만들어진 삼각형의 넓이를 구할 때, 방향이 모두 일정하다. 따라서 만들어진 삼각형의 넓이의 합이 곧 도형의 면적과 같다.

 

 

하지만 이 도형의 경우, 이처럼 점들을 순차적으로 접근하였을 때 방향이 뒤바뀌는 경우가 생기기때문에, 삼각형 넓이의 합이 도형의 면적과 같지 않게 된다. 그렇다면 이 경우에는 어떻게 도형의 면적을 구할 수 있을까?

우선 설명의 간편함을 위하여 도형을 아래와 같이 잘랐다.

그럼 이 도형을 점들을 순차적으로 접근하였을 때 생기는 삼각형들을 살펴보자.

순서대로 삼각형을 구하였을 때, 그 결과는 다음과 같다.

위 그림처럼 삼각형을 만들때, 겹치는 모습을 살펴볼 수 있다. 여기서 주목해야 하는 삼각형은 녹색 삼각형이고, 벡터의 외적을 이용하여 점들의 방향 관계를 구하였을 때, 나머지 삼각형의 경우 반시계 방향이지만 녹색 삼각형의 경우만 시계방향임을 알 수 있다. (CCW 알고리즘)

이제 위 도형들에서 혼자 반대방향인 녹색 삼각형을 빼보겠다.

우리가 구해야 하는 도형이 나왔다. 따라서 우리는 구해야 하는 도형이 오목한 다각형이라면 같은 방향끼리의 삼각형의 면적과 다른 방향끼리의 삼각형의 면적의 차를 구해야 한다는 것을 알게 되었다.

그렇다면 삼각형의 방향을 일일이 구하여 음수를 취해야 하는 것일까? 아니다

 

2차원 평면에서 벡터의 외적을 이용한다면 그 결괏값은 벡터 (0,0, z값)이 나오게 된다. 여기서 지금까지 우리가 삼각형의 면적(즉, 외적의 크기)을 구하기 위해 |z값|/2를 해준 셈이다.

 

여기서 절댓값을 취하지 않는다면, z값이 양수인 경우는 점들의 방향 관계가 반시계방향이고, 음수인 경우는 시계방향임을 알 수 있다. (CCW 알고리즘, 즉 외적의 z값이 같은 부호면 같은 방향)

즉, 어차피 음수값을 취하지 않더라도, 같은 방향의 면적들은 같은 부호의 값을 취함을 알 수 있다.

 

최종적으로 벡터의 외적을 구하여 2로 나누어 삼각형의 면적들을 더해주고, 최종적으로 마지막에 절댓값을 취하면 오목한 도형이라도 면적을 구할 수 있다.

 

코드는 다음과 같다.

 

import sys
 
 
def find_area(lst):
    area = 0
    for i in range(len(lst)-1):
        p1 = (lst[i][0] - lst[0][0], lst[i][1] - lst[0][1])
        p2 = (lst[i+1][0] - lst[0][0], lst[i+1][1] - lst[0][1])
 
        area += (p1[0] * p2[1] - p2[0] * p1[1])/2
 
    return round(abs(area),1)
 
 
n = int(sys.stdin.readline())
xy_list = []
 
for _ in range(n):
    xy_list.append(list(map(int,sys.stdin.readline().split())))
 
print(find_area(xy_list))

 

• 점들의 xy좌표를 입력받는다.
• find_area() 함수를 호출하여 도형의 면적을 구한다. 함수에 대한 설명은 다음과 같다.
• 0번 index의 x, y좌표를 기준으로 한다.
• 벡터 p1 = (1번 index의 x, y좌표) - (0번 index의 x, y좌표) , 벡터 p2 = (2번 index의 x, y좌표) - (0번 index의 x, y좌표)
• p1과 p2의 외적을 구한다.
• 2번 index와, 3번 index에 대하여도 위의 과정을 수행한다.
• 최종적으로 n번 index까지 위 과정을 수행하여 면적의 합을 구하고 절댓값을 취하여 반올림한다.