BOJ - 2166

BOJ - 2166 다각형의 면적

(문제 : https://www.acmicpc.net/problem/2166)

CCW(Counter Clock Wise) 알고리즘

1. 점 3개가 있을 때, 두 벡터를 서로 외적하면 평행사변형의 넓이임을 활용.
2. 각각의 점을 A, B, C로 가정할 때 vec(c, a), vec(a, b)의 외적을 하면 반시계 방향일 경우 값이 +, 시계 방향일 경우 값이 -, 직선일 경우 값이 0이 된다.

참고 : https://snowfleur.tistory.com/98

문제 해결 방법

CCW 알고리즘을 활용하여 문제 해결.

1. 한 점을 기준으로 다른 두 점과의 외적 결과를 바탕으로 삼각형의 넓이를 구한 뒤 모두 더해주면 다각형의 넓이가 된다.
2. 삼각형의 넓이 = 평행사변형 / 2
3. 외적의 음, 양은 만든 삼각형의 오목함과 볼록함을 판단할 때 사용함. 오목한 경우 전체 도형의 반대 값이 더해지므로 이 부분은 신경 안쓰고, 모든 벡터의 외적의 합을 구하면 답이 된다.
4. 결과 값은 음, 양에 구분없이 절대 값으로 구한다.

해결 및 최종 코드

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

public class Main {
	public static double stod(String s) {return Double.parseDouble(s);}
	public static int stoi(String s) {return Integer.parseInt(s);}
	public static class Point {
		double x, y;
		Point(double x, double y) {this.x = x; this.y = y;}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		int n = stoi(br.readLine());
		Point[] p = new Point[n];
		
		for(int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			
			p[i] = new Point(stod(st.nextToken()), stod(st.nextToken()));
		}
		
		double result = 0;
		
		for(int i = 1; i < n; i++) {
			result += ccw(p[0].x, p[i - 1].x, p[i].x, p[0].y, p[i - 1].y, p[i].y);
		}
		
		System.out.printf("%.1f",Math.abs(result));
	}
	
	public static double ccw(double x1, double x2, double x3, double y1, double y2, double y3) {
		return ((x1 * y2 + x2 * y3 + x3 * y1) - (y1 * x2 + y2 * x3 + y3 * x1)) / 2;
	}

}

후기

벡터를 활용한 기하학은 여전히 어렵다. 평면 좌표에서 넓이를 구하는 것과 벡터를 활용한 알고리즘들을 공부해야겠다.