BOJ_다각형의 면적_2166 (Java)

문제 링크

성능 요약

메모리: 19640 KB, 시간: 164 ms

분류

기하학, 다각형의 넓이

제출 일자

2025년 1월 2일 15:09:23

문제 설명

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

입력

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

출력

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

느낀점

• 세 점을 사용해 삼각형을 구하는 공식으로 모든 점을 순회하면서 각각의 삼각형 넓이를 더하면 되는거라고 생각했는데, 다각형의 면접을 구하는 공식으로도 사용할 수 있다는걸 알았다.
• 하지만 도형에 오목한 부분이 있다면 어떤 부분에서는 삼각형이 온전하지 않다.
• 따라서 다각형을 이루는 점만을 통해 모든 삼각형의 넓이를 단순히 모두 더하면 오목한 부분을 고려할 수 없다.
• 어려웠지만 다각형의 면적을 구하는 공식을 알 수 있어서 좋은 경험이었다.

설계 : 30분

• 한 점을 고정으로 두고 그 다음 두점씩 순서대로 순회하며 삼각형 면적 공식(신발끈 공식)을 적용한다.
• 이때 모든 삼각형마다 절대값 / 2 해서 더하면 오목한 부분을 고려할 수 없기 때문에 모두 더한 후에 절대값 / 2 한다.
• 신발끈 공식을 사용하면 삼각형 뿐만 아니라 다각형의 면적을 구할 수 있기 때문에 더 간단히 표현할 수도 있다.

코드(Java)

• 구현 시간: 70분 (모든 삼각형 너비 더하기)

/**
 * Author: yngbao97, Yuk Yejin
 * Problem: 다각형의 면적_2166
 * Date: 2025.01.02
 */

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

public class Main {
	static BufferedReader br;
	static BufferedWriter bw;
	static StringTokenizer st;

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

		br = new BufferedReader(new InputStreamReader(System.in));
		bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int n = Integer.parseInt(br.readLine());
		long[][] point = new long[n][2];
		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			long x = Long.parseLong(st.nextToken());
			long y = Long.parseLong(st.nextToken());
			point[i] = new long[] {x, y};
		}

		double sum = 0;
		for (int i = 1; i < n-1; i++) {
			sum += getArea(point[0], point[i], point[i+1]);
		}

		double answer = Math.abs(sum) / 2.00;
		bw.write(String.format("%.1f", answer));
		bw.flush();
		bw.close();
		br.close();
	}

	private static double getArea(long[] fixed, long[] first, long[] second) {
		return (fixed[0]*first[1] + first[0]*second[1] + second[0]*fixed[1]) - (first[0]*fixed[1] + second[0]*first[1] + fixed[0]*second[1]);
	}
}

• 구현 시간: 10분 (신발끈 공식)

/**
 * Author: yngbao97, Yuk Yejin
 * Problem: 다각형의 면적_2166
 * Date: 2025.01.02
 */

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

public class Main {
	static BufferedReader br;
	static BufferedWriter bw;
	static StringTokenizer st;

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

		br = new BufferedReader(new InputStreamReader(System.in));
		bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int n = Integer.parseInt(br.readLine());
		long[][] point = new long[n][2];
		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			long x = Long.parseLong(st.nextToken());
			long y = Long.parseLong(st.nextToken());
			point[i] = new long[] {x, y};
		}

		double sum = 0;
		for (int i = 1; i < n-1; i++) {
			sum += getArea(point[0], point[i], point[i+1]);
		}

		double answer = Math.abs(sum) / 2.00;
		bw.write(String.format("%.1f", answer));
		bw.flush();
		bw.close();
		br.close();
	}

	private static double getArea(long[] fixed, long[] first, long[] second) {
		return (fixed[0]*first[1] + first[0]*second[1] + second[0]*fixed[1]) - (first[0]*fixed[1] + second[0]*first[1] + fixed[0]*second[1]);
	}
}