[백준/11758] - CCW(JAVA)

2차원 좌표 평면 위에 있는 점 3개 P1, P2, P3가 주어진다. P1, P2, P3를 순서대로 이은 선분이 어떤 방향을 이루고 있는지 구하는 프로그램을 작성하시오.

입력

---

첫째 줄에 P1의 (x1, y1), 둘째 줄에 P2의 (x2, y2), 셋째 줄에 P3의 (x3, y3)가 주어진다. (-10,000 ≤ x1, y1, x2, y2, x3, y3 ≤ 10,000) 모든 좌표는 정수이다. P1, P2, P3의 좌표는 서로 다르다.

출력

---

P1, P2, P3를 순서대로 이은 선분이 반시계 방향을 나타내면 1, 시계 방향이면 -1, 일직선이면 0을 출력한다.

풀이

---

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int x1 = Integer.parseInt(st.nextToken());
		int y1 = Integer.parseInt(st.nextToken());
		st = new StringTokenizer(br.readLine());
		int x2 = Integer.parseInt(st.nextToken());
		int y2 = Integer.parseInt(st.nextToken());
		st = new StringTokenizer(br.readLine());
		int x3 = Integer.parseInt(st.nextToken());
		int y3 = Integer.parseInt(st.nextToken());
		System.out.println(ccw(x1, y1, x2, y2, x3, y3));

	}
	static int ccw(int x1, int y1, int x2, int y2, int x3, int y3) {
		int temp = x1*y2+x2*y3+x3*y1 - y1*x2-y2*x3-y3*x1;
		if (temp > 0) {
			return 1;
		} else if (temp < 0) {
			return -1;
		} else {
			return 0;
		}
	}
}

해설

---

CCW = Counter,Counter-ClockWise의 줄임말로, 시계방향과 시계 반대방향을 찾아내는 문제이다.

https://www.acmicpc.net/blog/view/27

점 3개의 방향성을 나타내는 CCW

를 읽어보자.

결론은 두 선분의 외적으로 방향을 구하는 것이다.

두 벡터를 외적하면 두 벡터에 수직인 벡터를 구할 수 있는데,

이 벡터가 위로 가는지, 아래로 가는지의 부호를 검사하는 것이다.

 

삼각형이나 넓이를 구하는 기본 알고리즘중에 신발끈 알고리즘이 있다.

기하쪽 문제를 풀 때에는 여지없이 등장하는 알고리즘이다.

삼각 이상의 다각형에서도 적용되는데, 다각형을 쪼개 삼각형으로 분할해 답을 도출해내는 방식이다.