[BaekJoon] 11758번 CCW (Java) 문제 풀이 [Gold 5]

문제

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

 

어떻게 풀 것인가?

문제 분석 : 큰 알고리즘 사용성에 대해서 보이지 않았다.

-> 그래서 우선 내가 알고 있는 수학과 구현이라는 관점에서 접근하였다.

 

방향을 알기위해서는 각도가 필요하다고 생각했다. (이 부분은 다른분의 해설을 참고하였다.)

 

이 과정에서 기하학 입문에서 다루어지는 신발끈 공식에 대해서 알게 되었다.

 

세 점이 주어졌을 때, 신발끈 공식을 사용하여 결과값이 0보다 크면 반시계 방향, 0이면 일직선, 0보다 작으면 시계 방향으로 구할 수 있다고 한다.

 

좀 더 자세하게 알아보자 .

신발끈 공식(또는 "shoelace theorem")은 주어진 점들이 이루는 다각형의 넓이를 구하는 방법으로 알려져 있지만, 이를 사용해서 세 점의 순서에 따른 방향을 구할 수도 있다. 세 점 P1(x1,y1), P2(x2,y2), P3(x3,y3)가 있을 때, 신발끈 공식을 이용한 방향 계산은 다음과 같이 할 수 있다.

 

결과 = x1y2 + x2y3 + x3y1 - (x2y1 + x3y2 + x1y3)

이 값을 통해 다음과 같은 결과를 도출할 수 있다:

• 결과 > 0: 반시계 방향 (Counter-clockwise)
• 결과 = 0: 일직선 (Collinear)
• 결과 < 0: 시계 방향 (Clockwise)
• 이 공식은 세 점을 기준으로 벡터의 외적을 계산하는 방식이다. 외적의 부호를 통해 세 점이 반시계 방향, 시계 방향, 일직선에 있는지를 판단할 수 있다.
• 외적이 양수이면 반시계 방향, 0이면 일직선, 음수이면 시계 방향으로 결정된다.

쉽게 말해, 이 공식을 사용하면 세 점의 순서에 따른 회전 방향을 빠르게 계산할 수 있다.

 

풀면서 놓쳤던점

수학 문제는 항상 어렵다...

 

이 문제를 통해 얻어갈 것

신발끈 공식

 

내 코드 

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

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st;
		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));

	}

	public static int ccw(int x1, int y1, int x2, int y2, int x3, int y3) {
		int a = x1 * y2 + x2 * y3 + x3 * y1;
		int b = y1 * x2 + y2 * x3 + y3 * x1;

		// 반시계 방향
		if (a - b > 0) {
			return 1;
		} else if (a == b) { // 평행
			return 0;
		} else { // 시계 방향
			return -1;
		}
	}

}

 

참고

https://steady-coding.tistory.com/217

[BOJ] 백준 11758번 : CCW (JAVA)