[BaekJoon] 11758 CCW

1.  문제 링크

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

2.  문제

요약

• 2차원 좌표 평면 위에 있는 세 점을 순서대로 이은 선분이 어떤 방향을 이루고 있는지 구하는 문제입니다.
• 입력: 첫 번째 줄에 첫 번째 점인 P1의 (x1, y1), 두 번째 줄에 두 번째 점인 P2의 (x2, y2), 세 번째 줄에 세 번째 점인 P3의 (x3, y3)가 주어집니다.
  • P1, P2, P3의 좌표는 모두 다르고 x1, y1, x2, y2, x3, y3는 -10,000보다 크거나 같고 10,000보다 작거나 같은 정수입니다.
• 출력: 첫 번째 줄에 P1, P2, P3를 순서대로 이은 선분이 반시계 방향이면 1, 시계 방향이면 -1, 일직선이면 0을 출력합니다.

3.  소스코드

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

public class Main {
	static int[][] points;
	
	public int getCCW() {
		int D = (points[1][0] - points[0][0]) * (points[2][1] - points[0][1]) - (points[1][1] - points[0][1]) * (points[2][0] - points[0][0]);
		if(D > 0) {
			return 1;
		} else if(D < 0) {
			return -1;
		} else {
			return 0;
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		points = new int[3][2];
		for(int i = 0; i < points.length; i++) {
			String[] input = br.readLine().split(" ");
			for(int j = 0; j < points[i].length; j++) {
				points[i][j] = Integer.parseInt(input[j]);
			}
		}
		br.close();
		Main m = new Main();
		bw.write(m.getCCW() + "\n");
		bw.flush();
		bw.close();
	}
}

4.  접근

• 평면 위 세 점의 방향관계를 구하는 CCW(Counter Clockwise) 알고리즘을 이용하여 문제를 해결할 수 있습니다.
• CCW 알고리즘은 P1, P2, P3 순서대로 봤을 때, 반시계 방향을 이루면 양수를, 시계 방향을 이루면 음수를, 평행하게 놓여있으면 0을 반환합니다.
• 두 벡터 $\vec{u} = (x_1, y_1, z_1), \vec{v} = (x_2, y_2, z_2)$의 외적 $\vec{u}$x$\vec{v}$은 $(y_1z_2 - z_1y_2, z_1x_2 - x_1z_2, x_1y_2 - y_1x_2)$가 됩니다.
• 두 벡터의 외적을 이용하여 세 점의 방향관계를 구합니다.
• $P_1 = (x_1, y_1, 0), P_2 = (x_2, y_2, 0), P_3 = (x_3, y_3, 0)$ 세 점을 이용하여 $\vec{a} = \overrightarrow{P_1P_2} = (x_2 - x_1, y_2 - y_1, 0), \vec{b} = \overrightarrow{P_1P_3} = (x_3 - x_1, y_3 - y_1, 0)$ 두 벡터를 생성합니다.
• 두 벡터 $\vec{a}, \vec{b}$의 외적 $\vec{a}$x$\vec{b}$은 위 공식에 의하여 $(0, 0, (x_2 - x_1)(y_3 - y_1) - (y_2 - y_1)(x_3 - x_1))$이 됩니다.
• 두 벡터의 외적은 오른손 법칙을 따릅니다.

• 위에서 세 점 $P_1, P_2, P_3$를 통해 구한 두 벡터 $\vec{a}, \vec{b}$를 기준으로 생각해보면 $\vec{a}$ 방향으로 엄지를 제외한 네 손가락을 두고 $\vec{b}$ 방향으로 손바닥을 뒀을 때, 엄지 손가락 방향이 두 벡터 $\vec{a}, \vec{b}$ 외적의 방향이 됩니다.
• 오른손 법칙에 따라 외적의 결과가 양수일 때는 반시계 방향이 되고 외적의 결과가 음수일 때는 시계 방향이 되며 외적의 결과가 0일 때는 일직선이 되게 됩니다.

1. 주어진 세 점에 대해 위에서 구한 CCW 알고리즘을 이용하여 외적의 결과를 구합니다.
2. 만약 외적의 결과가 음수라면 시계 방향을 의미하므로 -1을 출력하고 양수라면 반시계 방향을 의미하므로 1을 출력하며 만약 결과가 0이라면 일직선 상에 있음을 의미하기 때문에 0을 출력합니다.