백준 2166 다각형의 면적 [자바]

in Develop / Solving

baekjoon 2166 다각형의 면적

java

문제 분석

  • N개의 점으로 이루어진 다각형
  • N개의 점을 다각형을 이루는 순서대로 줄 때, 다각형의 넓이는?

입력조건

좌표의 수 N
N개의 줄에 걸쳐서 {
	다각형의 좌표 r c
}

풀이과정

  • 이 문제의 핵심은 좌표를 다각형을 이루는 순서대로(시계방향)으로 준다는 것. 이 조건 덕에 신발끈 공식을 이용할 수 있다.

  • 신발끈 공식? 좌표로 다각형의 위치가 주어질 때, 넓이를 구할 수 있는 식이다. 자세한 공식은 아래와 같다.

    1. 다각형의 좌표를 시계방향 혹은 반시계방향으로 나열하고, 첫 좌표를 맨 밑에 다시 적는다.

    2. i번째 좌표의 x좌표와, i+1번째 행의 y좌표를 곱하여 다 더한다.

    3. i번째 y좌표와, i+1번째 x좌표를 곱하여 다 더한다.

    4. 2, 3에서 구한 값을 빼고 2로 나누면 넓이를 구할 수 있다.

  • 각 좌표는 100,000 이하의 수지만 이를 int로 받고 연산할 시, 연산 과정에서 int를 초과하는 결과가 발생해서 오답이 나오게 된다. 그러므로 long으로 입력을 받고,

  • 소수의 경우 double로 처리한다.

코드 구성

  • 신발끈 공식

    long suma = 0;
long sumb = 0;
for(int i = 0; i < N; i++) {
    suma += map[i][0] * map[i+1][1];
    sumb += map[i][1] * map[i+1][0];
}
System.out.printf("%.1f",Math.abs(((suma - sumb)/2.0d)));

전체 코드

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

public class BJ2166_다각형의면적 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		long[][] map = new long[N+1][2];
		for(int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			map[i][0] = Integer.parseInt(st.nextToken());
			map[i][1] = Integer.parseInt(st.nextToken());
		}
		map[N][0] = map[0][0];
		map[N][1] = map[0][1];
		
		long suma = 0;
		long sumb = 0;
		for(int i = 0; i < N; i++) {
			suma += map[i][0] * map[i+1][1];
			sumb += map[i][1] * map[i+1][0];
		}
		System.out.printf("%.1f",Math.abs(((suma - sumb)/2.0d)));
	}
}

추가

  • 자료형 때문에 여러 번 틀린 후 답을 맞췄다.ㅜㅠ
  • 데이터가 작게 들어오면, 실버로 내려가도 될 것이라 생각한다. 크게 어렵지 않고, 코드양도 길지 않았다.