[BOJ] 2166 다각형의 면적 - JAVA

1. 문제

2166번: 다각형의 면적

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

---

2. 풀이

이 문제에서 알아야 하는 지점은 2가지다.
1. 좌표타입 : 좌표는 int타입으로 입력받지만, 저장을 long으로 하거나 계산중에 long으로 계속 바꿔야한다. 그렇지 않으면 범위 초과될 가능성이 있다. (10만 * 10만 * 1만개 점)
2. 신발끈 공식 : 설명은 위키백과로 대신한다.

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

import java.io.*;
import java.util.*;

public class BOJ_2166_다각형의면적 {
   public static void main(String[] args) throws IOException {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st;

      int N = Integer.parseInt(in.readLine());

      long[][] coordinate = new long[N+1][2];
      for(int i=0;i<N;i++){
         st = new StringTokenizer(in.readLine());
         coordinate[i][0] = Integer.parseInt(st.nextToken());
         coordinate[i][1] = Integer.parseInt(st.nextToken());
      }
      coordinate[N] = coordinate[0];

      long area = 0;
      for(int i=0;i<N;i++){
         area += coordinate[i][0]*coordinate[i+1][1];
         area -= coordinate[i+1][0]*coordinate[i][1];
      }

      System.out.printf("%.1f",Math.abs(area)*0.5);
   }
}

---

3. 결과

여러 개의 삼각형 너비를 합치면 된다고 생각했는데, 그렇게 구하면 오목다각형 넓이를 구할 수 없다.