2166 - 다각형의 면적

이 문제는 다각형을 이루는 점의 좌표가 차례대로 주어졌을 때, 그 다각형의 넓이를 구하는 문제이다.

흔히 알려진 신발끈 공식을 사용하면 이 문제를 풀 수 있다. 다각형의 정점을 $P_1 (x_1, y_1), \ P_2(x_2, y_2), \ \cdots P_n(x_n, y_n)$ 으로 두면

$$S = \frac{1}{2} \left | \begin{matrix} x_1 & x_2 & \cdots & x_n & x_1 \\ y_1 & y_2 & \cdots & y_n & y_1 \end{matrix} \right |$$

이다.

즉 풀어쓰면

$$S = \frac 1 2 | (x_1y_2 + x_2y_3 + \cdots + x_{n-1}y_n + x_n y_1) - (x_2y_1 + x_3y_2 + \cdots + x_ny_{n-1} + x_1y_n) |$$

이다.

🔗문제 링크

코드

먼저 꼭짓점의 개수를 입력받는다. 그런 다음 오른쪽 아래($\searrow$) 방향으로 곱한 값들의 합과 왼쪽 아래($\swarrow$) 방향으로 곱한 값들의 합을 저장할 rightDir, leftDir을 각각 변수로 선언한다.

참고로 long을 쓰는 이유는 이 문제의 꼭짓점에 대한 최대 좌표가 100000이어서 오버플로우 가능성이 있기 때문이다. 예를 들어 한 변의 길이가 100000인 정사각형의 넓이를 구하면 $10^{10}$인데 이는 어림잡아 $2^{33}$ 보다 더 큰 값이므로 int로는 오버플로우가 발생할 것이다. 따라서 long을 써줘야 한다.

public static void main(String[] args) throws IOException {
    int N = Integer.parseInt(br.readLine());
    long leftDir = 0;
    long rightDir = 0;

처음으로 입력받은 꼭짓점은 firstX, firstY에 저장해둔다. 이는 추후 맨 마지막 꼭짓점과 첫 꼭짓점을 가지고 연산하는 항이 있기 때문이다. 그런 다음 prevX = firstX, prevY = firstY로 대입한다.

    StringTokenizer st = new StringTokenizer(br.readLine());
    long firstX = Long.parseLong(st.nextToken());
    long firstY = Long.parseLong(st.nextToken());
    long prevX = firstX;
    long prevY = firstY;

이제 루프를 N-1번 돌며 2번 꼭짓점부터 N번 꼭짓점까지 위치를 입력받아 각 대각선 방향별로 항을 계산한다. 연속적으로 항을 계산하기 위해 현재 입력받은 curX, curY를 prevX, prevY에 대입한다.

루프를 빠져나오면 N번째 꼭짓점과 1번째 꼭짓점을 이용한 마지막 항을 계산해 더해준다.

    for (int i = 1; i < N; i++) {
        st = new StringTokenizer(br.readLine());
        long curX = Long.parseLong(st.nextToken());
        long curY = Long.parseLong(st.nextToken());

        rightDir += prevX * curY;
        leftDir += prevY * curX;
        prevX = curX; prevY = curY;
    }

    rightDir += prevX * firstY;
    leftDir += prevY * firstX;

마지막으로 rightDir-leftDir을 계산한 뒤 절댓값을 씌우고, 2로 나눠 다각형의 최종 넓이를 구한다. 문제에서 소수점 한 자리까지 반올림하라고 했으므로 %.1f로 포매팅해 출력한다.

    double result = Math.abs(rightDir-leftDir)/2.0D;
    System.out.printf("%.1f", result);
}

전체 코드

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

class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        int N = Integer.parseInt(br.readLine());
        long leftDir = 0;
        long rightDir = 0;

        StringTokenizer st = new StringTokenizer(br.readLine());
        long firstX = Long.parseLong(st.nextToken());
        long firstY = Long.parseLong(st.nextToken());
        long prevX = firstX;
        long prevY = firstY;
        for (int i = 1; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            long curX = Long.parseLong(st.nextToken());
            long curY = Long.parseLong(st.nextToken());

            rightDir += prevX * curY;
            leftDir += prevY * curX;
            prevX = curX; prevY = curY;
        }

        rightDir += prevX * firstY;
        leftDir += prevY * firstX;

        double result = Math.abs(rightDir-leftDir)/2.0D;
        System.out.printf("%.1f", result);
    }


}

시간복잡도

루프는 $N-1$번 돌기 때문에 시간복잡도는 $O(N)$이다.