[Algorithm][파이썬] 백준 11758번: CCW

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

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) 알고리즘:

평면의 점 3개가 주어지고 이 점3개를 이은 직선의 방향을 구하는 기하 알고리즘

직선의 방향은 시계 방향, 반시계 방향, 직선 3가지로 외적을 통하여 구한다.

 

세 점의 좌표를 각각 (x1,y1),(x2,y2),(x3,y3)라고 할 때, 방향 관계식

x1y2 + x2y3 + x3y1 - (x2y1 + x3y2 + x1y3)

 

결과 값 양수 = 반시계 방향 (sin 값이 양수이므로)

결과 값 음수 = 시계 방향 (sin 값이 음수이므로)

결과 값 0 = 직선 (sin 값이 0이므로)

 

코드

코드 출처: https://lbdiaryl.tistory.com/m/190

def CCW(p1,p2,p3): #방향 관계식
    A=p1[0]*p2[1]+p2[0]*p3[1]+p3[0]*p1[1]
    B=p1[1]*p2[0]+p2[1]*p3[0]+p3[1]*p1[0]

    if A-B==0:     #직선
        return 0
    elif A-B>0:    #반시계 방향
        return 1
    else:          #시계 방향
        return -1

P1=list(map(int,(input().split())))
P2=list(map(int,(input().split())))
P3=list(map(int,(input().split())))

print(CCW(P1,P2,P3))

 

기하를 배운 적이 없어서 외적 자체도 이해하기 힘들었던 문제였다.

평소 문제를 풀던 언어인 C언어나 JAVA로는 도저히 이해가 가지 않아서

그나마 코드 길이가 짧은 파이썬으로 문제를 이해했다.