[백준] 2166번 : 다각형의 면적 (java)

2166번: 다각형의 면적 (acmicpc.net)

2166번: 다각형의 면적

어떻게 생각하고 문제를 풀었는가?

3~10,000개의 점으로 이루어진 다각형은 각 꼭짓점을 이어 만든 1개 이상의 삼각형으로 표현할 수 있습니다.

따라서 0번째 점을 기준점으로 잡고 시계방향으로 겹치지 않는 삼각형의 너비를 모두 합한다면 다각형의 너비를 찾을 수 있다고 생각하였습니다.

코드

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

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(reader.readLine());
        Position[] positions = new Position[N];
        for(int i=0; i<N; i++){
            StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
            long x = Long.parseLong(tokenizer.nextToken());
            long y = Long.parseLong(tokenizer.nextToken());
            positions[i] = new Position(x, y);
        }
        reader.close();

        long area = 0;
        for(int i=1; i+1<N; i++){
            area += outerProduct(positions[0], positions[i], positions[i+1]);
        }
        area = Math.abs(area);
        System.out.printf("%.1f\n", (double) area/2);
    }

    static long outerProduct(Position first, Position second, Position third){
        return (first.x * second.y + second.x * third.y + third.x * first.y) - (first.x * third.y + second.x * first.y + third.x * second.y);
    }

    static class Position {
        long x;
        long y;
        public Position(long x, long y){
            this.x = x;
            this.y = y;
        }
    }
}

외적을 사용하여 너비를 구하는 코드를 작성하였습니다.

3개의 점의 x, y좌표로부터 외적으로 각 삼각형의 너비를 구하고 이를 합하여 다각형의 너비를 반환합니다.