[백준]다각형의 면적 2166 - JAVA

1. 1. 문제

 

 

2. 2. 접근

다각형은 삼각형으로 구성되니깐 한 점을 고정 시킨 다음 두 점을 이동시켜서 삼각형의 넓이를 구해주면 되겠구나 했다.

근데 계속해도 틀렸다고 나오길래 포기했다.

 

나는 처음 들어보는 신발끈 공식을 이용하는 풀이였다. 삼각형은 왜 안되나 봤더니 아래그림에서 점 P2, P3, P4으로 삼각형의 넓이 공식을 적용하면 제대로 된 넓이를 구할 수 없었다.

 

 

신발끈 공식은 시계 반대(정) 방향으로 돌면서 두 점을 정해 각 x, y를 곱해주어서 빼준다. 이때 마지막 점은 다시 첫 점으로 돌아와야 한다.

코드로 구현하면 다음과 같다.

      

      

      

    
    

      <java />
    
for(int i=0; i<N; i++){
            Point p1 = points.get(i);
            Point p2 = points.get((i+1)%N);

            sum += p1.x*p2.y - p2.x*p1.y;
        }

        bw.write( String.format("%.1f", Math.abs(sum)/2.0));

 

이때 중요한 점은 sum에다가 값을 더할 때 절대값으로 붙이면 안되는 것이다. 다 더한 다음에 결과에 절대값을 붙여야한다. 부호가 다른 것도 다 적용해야지 제대로 된 값이 나온다. 그리고 마지막에 2로 나눠주면 다각형의 넓이가 나온다. 주의할 점은 결과가 Int 범위를 초과하니 long으로 선언해줘야 한다.

 

3. 3. 전체 코드

      

      

      

    
    

      <java />
    
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

class Main {
    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {

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

        List<Point> points = new ArrayList<>();

        for(int i=0; i<N; i++){
            String [] str = br.readLine().split(" ");
            int x = Integer.parseInt(str[0]);
            int y = Integer.parseInt(str[1]);

            points.add(new Point(x, y));
        }


        double sum = 0.0;
        for(int i=0; i<N; i++){
            Point p1 = points.get(i);
            Point p2 = points.get((i+1)%N);

            sum += (double)p1.x*p2.y - (double)p2.x*p1.y;
        }

        bw.write( String.format("%.1f", Math.abs(sum)/2.0));
        bw.flush();
    }

}

class Point{
    int x;
    int y;

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