[백준] 다각형의 면적 (신발끈 공식, 기하학) - JAVA

class5

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

 

 

 

 

# 문제

2차원 평면상에 N(3 ≤ N ≤ 10,000)개의 점으로 이루어진 다각형이 있다. 이 다각형의 면적을 구하는 프로그램을 작성하시오.

 

# 예제

입력 :  첫째 줄에 N이 주어진다. 다음 N개의 줄에는 다각형을 이루는 순서대로 N개의 점의 x, y좌표가 주어진다. 좌표값은 절댓값이 100,000을 넘지 않는 정수이다.

4
0 0
0 10
10 10
10 0

 

출력 :  첫째 줄에 면적을 출력한다. 면적을 출력할 때에는 소수점 아래 둘째 자리에서 반올림하여 첫째 자리까지 출력한다.

100.0

 

# 필요개념

처음 문제를 풀 때 "다각형을 이루는 순서대로"라는 조건을 보지 못해서 배열에 어떻게 담아야 할지 고민이 많았다! 그런데 다각형을 이루는 순서대로 주어지니 한결 쉬워졌다.

 

다각형의 면적을 구할 때 쓰는 대표적인 공식인 신발끈 공식을 사용해 문제를 풀었다. 신발끈 공식을 사용할 때 가장 중요한 부분이 배열에 점을 어떤 순서대로 담는가 이다. 꼭 다각형을 이루는 순서대로 배열에 좌표를 넣어주어야 한다. 

 

만약 P1, P2, P3, P4, P5 를 갖는 오각형이 있다면, P1부터 시계방향인 P2, P3.... 순으로 넣거나 반시계방향인 P5, P4.. 순서로 넣어주어야 한다. 

 

x	x1	x2	x3	x4	x5
y	y1	y2	y3	y4	y5

 

이렇게 값이 들어가 있다면 신발끈 공식을 사용할 수 있다. 공식은 아래와 같다.

|(x1y2 + x2y3 + x3y4 + x4y5 + x5y1) - (x2y1 + x3y2 + x4y3 + x5y4 + x1y5)| / 2

 

추가로 위 값은 int형을 벗어나기 때문에 long타입으로 써주어야 한다는 것을 알아두자

 

# Code

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());
        int[][] inputs = new int[2][N];
        for (int i = 0 ; i < N ; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            inputs[0][i] = Integer.parseInt(st.nextToken());
            inputs[1][i] = Integer.parseInt(st.nextToken());
        }
        long solution = 0L;
        for (int i = 0 ; i < N ; i++) {
            solution += (long) inputs[0][i] * inputs[1][(i + 1) % N];
            solution -= (long) inputs[1][i] * inputs[0][(i + 1) % N];
        }

        String sol = String.format("%.1f", Math.abs(solution) / 2.0);
        bw.write(sol);
        bw.flush();
        bw.close();
    }
}

 

# 결과