백준 2166번: 다각형의 면적(Java, 기하)

HamJina·2025년 7월 31일

백준

목록 보기

8/17

☑️ 문제

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

✔️관련 알고리즘 개념

Shoelace 공식(Shoelace formula)

2차원 평면에서 다각형의 면적을 구하는 공식으로, 점들이 순서대로(시계 혹은 반시계 방향) 주어졌을 때 사용할 수 있다.

🥾 Shoelace 공식 (신발끈 공식)

다각형의 꼭짓점이 다음과 같이 순서대로 주어졌다.

$(x1,y1), (x2,y2), (x3,y3), …, (xn,yn)$

이때, 면적 A는 다음과 같은 신발끈 공식으로 계산된다.

단, 여기에 끝 점의 다음 점으로 시작점을 다시 사용해야 하므로:

$xn+1=x1$
$yn+1=y1$ 이 된다.

☑️ 문제 분석

해당 문제는 N각형을 나타내는 N개의 좌표가 주어졌을 때 해당 다각형의 면적을 구하는 문제이다.
처음에는 N각형을 쪼개서 삼각형을 만든 다음 각 삼각형의 넓이를 |CCW|/2를 이용하여 구한 다음 다 더해서 N각형의 넓이를 구하려고 했는데 이는 좌표가 시계방향 혹은 반시계 순서대로 주어져야 사용할 수 있다.
N각형의 넓이를 삼각형으로 쪼개지 않고 바로 구할 수 있는 방법은 신발끈 공식을 이용하여 문제를 푼다.

단 여기서 주의해야 할 것은 i값이 n일 때 i+1값은 존재하지 않으므로 x1, y1값으로 계산해야 한다는 점이다.

☑️ 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        Coordinates[] p = new Coordinates[N];
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            p[i] = new Coordinates(a, b);
        }

        double result = 0;
        for (int i = 0; i < N; i++) {
            int j = (i + 1) % N; // 다음 점, 마지막 → 첫 점으로 순환
            result += (long)p[i].x * p[j].y - (long)p[j].x * p[i].y;
        }

        System.out.printf("%.1f\n", Math.abs(result) / 2.0);
    }

    public static class Coordinates {
        int x, y;
        Coordinates(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}