[BOJ] 백준 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을 출력한다.

 

 

풀이

기하학의 기초 알고리즘인 CCW 입문 문제입니다.

 

 

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

 

신발끈 공식은 아래와 같이 행하는 것입니다.

 

 

 

 

먼저, 빨간색 빗금을 곱셈해서 더해줍니다.

 

x1y2 + x2y3 + x3y1 이 되겠죠.

 

 

 

 

그리고 난뒤 파란색 빗금을 곱셈하서 더해줍니다.

 

x2y1 + x3y2 + x1y3 가 되겠죠.

 

 

마지막으로, 빨간색 빗금으로 구한 것과 파란색 빗금으로 구한 것을 서로 빼면 CCW를 구하는 공식이 됩니다.

 

정리하면, x1y2 + x2y3 + x3y1 - (x2y1 + x3y2 + x1y3) 라고 할 수 있습니다.

 

 

아래는 위 과정을 정리한 소스코드입니다.

 

 

소스코드

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.

 

 

참고 사이트

[알고리즘] CCW로 세 점의 방향성 판별하기