[Python/Baekjoon] 11758번: CCW

문제

---

 

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(Counter Clock Wise) algorithm

선분 교차 판별로, 점 3개를 이은 선의 방향성 또는 세 점에 대한 위치 관계를 알 수 있는  기하 알고리즘이다.

 

참고

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

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

 

 

p = []
for i in range(3):
    p.append(list(map(int, input().split())))

def ccw(dot1, dot2, dot3):
    x1, y1 = dot1
    x2, y2 = dot2
    x3, y3 = dot3
    return (x1 * y2 + x2 * y3 + x3 * y1) - (x2 * y1 + x3 * y2 + x1 * y3)

result = ccw(p[0], p[1], p[2])
if result > 0:
    print(1)
elif result < 0:
    print(-1)
else:
    print(0)

ccw 함수) 1, 2, 3 번째의 좌표를 x, y에 저장하고 행렬의 신발끈 공식을 활용하여 리턴값을 지정한다.

메인 함수) 리턴값의 결과(양수, 0, 음수)에 따라서 출력한다.

 

CCW 알고리즘에 대해 잘 알면 코드 짜는 건 어렵지 않다.

그치만 난 아직 다른 문제에서 유연히 사용하기가 어려울 것으로 예상된다.