[BOJ] 1198 삼각형으로 자르기 - JAVA

1. 문제

1198번: 삼각형으로 자르기

볼록 다각형이 있고, 여기서 3개의 연속된 점을 선택해서 삼각형을 만든다. 그 다음, 만든 삼각형을 다각형에서 제외한다. 원래 다각형이 N개의 점이 있었다면, 이제 N-1개의 점으로 구성된 볼록 다각형이 된다. 위의 과정은 남은 다각형이 삼각형이 될 때까지 반복한다.

볼록 다각형의 점이 시계 방향순으로 주어진다. 마지막에 남은 삼각형은 여러 가지가 있을 수 있다. 이때, 가능한 넓이의 최댓값을 구하는 프로그램을 작성하시오.

첫째 줄에 볼록 다각형 점의 수 N (3 ≤ N ≤ 35)이 주어진다. 둘째 줄부터 N개의 줄에는 볼록 다각형을 이루고 있는 점이 시계 방향 순서로 주어진다. 좌표는 10,000보다 작거나 같은 자연수이다.

첫째 줄에 문제의 정답을 출력한다. 절대/상대 오차는 10-9까지 허용한다.

---

2. 풀이

1.  좌표를 모두 points에 저장한다.

2.  선택된 세 개의 좌표를 저장하기 위한 selected 배열을 초기화한다.

3.  조합(pick 함수)으로 점 세개를 뽑은 뒤 넓이를 구해서 비교한다. 아래 공식을 활용했다.

4.  최대값을 출력한다.

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

public class BOJ_1198_삼각형으로자르기 {
   static int N;
   static double MAX = 0;
   static int[][] points;
   static int[][] selected;
   public static void main(String[] args) throws IOException {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      N = Integer.parseInt(in.readLine());
      points = new int[N][2];
      StringTokenizer st;
      for(int i=0;i<N;i++){
         st = new StringTokenizer(in.readLine());
         points[i][0] = Integer.parseInt(st.nextToken());
         points[i][1] = Integer.parseInt(st.nextToken());
      }
      selected = new int[3][2];
      pick(0,0);
      System.out.println(MAX);
   }
   private static void pick(int cnt, int start){
      if(cnt==3){
         //넓이 구하기
         double area = (selected[0][0]*selected[1][1]+selected[1][0]*selected[2][1]+selected[2][0]*selected[0][1])
               -(selected[0][0]*selected[2][1]+selected[2][0]*selected[1][1]+selected[1][0]*selected[0][1]);
         if(area<0) area *= -1;
         area/=2;
         //비교하기
         MAX = Math.max(MAX,area);
         return;
      }

      for(int i=start;i<N;i++){
         selected[cnt] = points[i];
         pick(cnt+1,i+1);
         selected[cnt] = null;
      }
   }
}

---

3. 결과