[BaekJoon] 2166 다각형의 면적 (Java)

1.  문제 링크

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

2.  문제

요약

• 2차원 평면상에 N개의 점으로 이루어진 다각형이 있는데, 이 다각형의 면적을 구하는 문제입니다.
• 입력: 첫 번째 줄에 3보다 크거나 같고 10,000보다 작거나 같은 N이 주어지고 두 번째 줄부터 N개의 줄에는 -100,000보다 크거나 같고 100,000보다 작거나 같은 정수인 N개의 점의 좌표 x, y가 주어집니다.
• 출력: 첫 번째 줄에 면적을 출력합니다. 면적을 출력할 때에는 소숫점 아래 둘째 자리에서 반올림하여 첫째 자리까지 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
	public long getWidth(Point p1, Point p2, Point p3) {
		return ((p1.x * p2.y + p2.x * p3.y + p3.x * p1.y) - (p2.x * p1.y + p3.x * p2.y + p1.x * p3.y));
	}
	
	public double getWidthOfPolygon(Point[] points) {
		long result = 0;
		for(int i = 1; i < points.length - 1; i++) {
			result += getWidth(points[0], points[i], points[i + 1]);
		}
		result = Math.abs(result);
		return (double)result / 2;
	}
	
	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 num = Integer.parseInt(br.readLine());
		Point[] points = new Point[num];
		for(int i = 0; i < num; i++) {
			String[] input = br.readLine().split(" ");
			points[i] = new Point(Long.parseLong(input[0]), Long.parseLong(input[1]));
		}
		br.close();
		Main m = new Main();
		double result = m.getWidthOfPolygon(points);
		bw.write(String.format("%.1f", result) + "\n");
		bw.flush();
		bw.close();
	}
	
	static class Point {
		long x, y;
		public Point(long x, long y) {
			this.x = x;
			this.y = y;
		}
	}
}

4.  접근

• 다각형의 넓이는 벡터의 외적을 이용하여 구합니다.
• 다각형에서 점 하나를 기준으로 잡고 기준점을 중심으로 CCW를 돌면서 다각형을 삼각형으로 나눕니다.
• 나눈 삼각형의 면적은 구할 수 있기 때문에 이를 이용하여 다각형의 넓이를 구합니다.
• 방향과 관련이 있는 외적이므로 모든 값들을 더한 후에 마지막에 절댓값을 씌워야 합니다.

1. 점의 x좌표, y좌표를 멤버변수로 갖는 클래스 Point를 생성하고 주어진 N개의 점들을 1차원 배열 points에 넣습니다.
2. 주어진 다각형의 넓이를 나타내는 변수 result를 생성하고 값을 0으로 초기화합니다.
3. points의 두 번째 점부터 (N - 1)번째 점까지 반복문을 돌며 다각형의 넓이를 구합니다.
   1. 첫 번째 점을 기준으로 현재 점과 바로 다음 점과의 CCW를 구합니다.
   2. 현재 점에서의 CCW 값을 result에 더해줍니다.
4. 3번 반복문이 끝난 후의 result값에 절댓값을 씌워 해당 값을 출력합니다.