[2166] 다각형의 면적

✔ 다각형의 면적

[백준 2166]

문제 분석하기

CCW는 벡터의 외적값을 의미하기도 하므로 CCW의 절댓값은 세 점의 벡터 외적이고,

세 점을 기준으로 하는 평행사변형의 넓이를 나타냄

즉, CCW의 절댓값을 2로 나누면 세 점을 꼭짓점으로 하는 삼각형의 넓이를 알 수 있음

결국 다각형의 넓이는 원점과 다른 두 점 간의 CCW로 구할 수 있음

손으로 풀어보기

1. 원점과 순서대로 나오는 두 점 사이의 CCW값을 계산
2. 결과의 총합을 절댓값으로 변경한 후 2로 나눠 정답을 구함

예) 0 0, 0 10, 10 10, 10 0

슈도코드 작성하기

N(점의 개수)
x[](x 좌표 저장하기) y[](y 좌표 저장하기)
for(i -> 0 ~ N - 1) {
    배열에 x, y 좌표 저장하기
}
x[N] = x[0]
y[N] = y[0]
for(i -> 0 ~ N) {
    result += (x[i] * y[i + 1]) - (x[i + 1] * y[i])
}
result값을 2로 나누고 둘째 자리 반올림해 출력하기

코드 구현하기

/**
 * 2166) 다각형의_면적
 */
public class D100_2166 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // N(점의 개수)
        int N = sc.nextInt();
        // x[](x 좌표 저장하기)
        long[] x = new long[N + 1];
        // y[](y 좌표 저장하기)
        long[] y = new long[N + 1];
        // 배열에 x, y 좌표 저장하기
        for (int i = 0; i < N; i++) {
            x[i] = sc.nextInt();
            y[i] = sc.nextInt();
        }
        // 배열의 마지막에 처음 점 다시 넣기
        // 마지막 점과 처음 점도 CCW 계산에 포함되도록 함
        x[N] = x[0];
        y[N] = y[0];
        double result = 0;
        // 원점, i, i + 1 세 점과 관련된 CCW 값을 구해 result에 더하기
        for (int i = 0; i < N; i++) {
            result += (x[i] * y[i + 1]) - (x[i + 1] * y[i]);
        }
        // result값을 2로 나누고 둘째 자리 반올림해 출력하기
        String answer = String.format("%.1f", Math.abs(result) / 2.0);
        System.out.println(answer);
    }
}