[BOJ/JAVA] 1198번: 삼각형으로 자르기

1198번: 삼각형으로 자르기

https://www.acmicpc.net/problem/1198

키워드

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

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

---

구현

문제에서는 삼각형을 계속 제거해 나갔지만 결국은 볼록 다각형의 3점으로 만들 수 있는 삼각형 넓이의 최댓값과 동일한 문제이다.

N개의 점에서 3개를 선택하여 해당 삼각형의 넓이의 최댓값을 구한다.

3 점을 이용하여 삼각형의 넓이를 구하는 공식은 다음과 같다.

$$S = {1\over2}|(x_1y_2+x_2y_3+x_3y_1)-(x_1y_3+x_3y_2+x_2y_1)|$$

이를 이용하여 넓이의 최댓값을 계산하자

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class java_1198 {
    static int N;
    static Pair pairs[];

    private static class Pair {
        int y;
        int x;

        public Pair(int y, int x) {
            this.y = y;
            this.x = x;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());

        pairs = new Pair[N];

        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());

            Pair pair = new Pair(y, x);

            pairs[i] = pair;
        }

        double result = solution();

        System.out.println(result);

        br.close();
    }

    // 가능한 삼각형 넓이 최댓값 구하기
    // N^3
    private static double solution() {
        double result = 0;

        for (int first = 0; first < N - 2; first++) {
            for (int second = first + 1; second < N - 1; second++) {
                for (int third = second + 1; third < N; third++) {
                    double tmpWidth = calcTriangle(pairs[first], pairs[second], pairs[third]);
                    result = Math.max(result, tmpWidth);
                }
            }
        }

        return result;
    }

    // 3 점으로 삼각형 넓이 계산하기
    private static double calcTriangle(Pair a, Pair b, Pair c) {
        double result = 0d;

        double first = a.x * b.y + b.x * c.y + c.x * a.y;
        double second = b.x * a.y + c.x * b.y + a.x * c.y;

        result = 0.5 * Math.abs(first - second);

        return result;
    }
}

---

Uploaded by N2T