2. 백준 Python[11758] CCW

[11758] CCW

---

 

난이도: Gold 5

시도횟수: 2

www.acmicpc.net/problem/11758

11758번: CCW

문제

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

 

---

제출한 코드(1) - 틀렸습니다.

import math
import sys
x1, y1=map(int, sys.stdin.readline().split())
x2, y2=map(int, sys.stdin.readline().split())
x3, y3=map(int, sys.stdin.readline().split())
p_angle=math.atan2((y2-y1),(x2-x1))
s_angle=math.atan2((y3-y2),(x3-x2))

if (s_angle)==(p_angle):
    print(0)
elif p_angle>=0:
    if s_angle<p_angle and s_angle>p_angle-math.pi:
        print(-1)
    elif s_angle==p_angle-math.pi:
        print(0)
    else:
        print(1)
else:
    if s_angle>p_angle and s_angle<p_angle+math.pi:
        print(1)
    elif s_angle==p_angle+math.pi:
        print(0)
    else:
        print(-1)

처음에는 P1P2, P2P3 벡터를 이용하여 x축과 이루는 각을 atan2() 함수를 이용하여 잰 뒤, 첫번째 벡터를 기준으로 왼쪽인지, 오른쪽인지를 판단하여 방향을 판별하려했습니다.

 

웬만한 test case에서 모두 성공을 했지만 제출 시 실패가 떴네요. 아마 math.atan2()와 math.pi를 이용하는 과정에서 두 벡터의 크기가 너무 큰 경우 오차가 발생하여 두 벡터 각도가 잘 판정되지 않아서 그런 것 같습니다.

 

이후 회전행렬을 이용한 풀이도 생각해보았지만 오차 발생은 마찬가지일 것 같아서 쓰지 않았습니다.

---

제출한 코드(2)

import sys
x1, y1=map(int, sys.stdin.readline().split())
x2, y2=map(int, sys.stdin.readline().split())
x3, y3=map(int, sys.stdin.readline().split())

triangle=(x2-x1)*(y3-y1)-(y2-y1)*(x3-x1)
if triangle==0:
    print(0)
elif triangle>0:
    print(1)
else:
    print(-1)

결국 CCW관련 힌트를 봤습니다 ㅠ

두 벡터를 외적하면 회전 방향을 알 수 있다는 점을 이용해야 했습니다.

고등학교 기하와 벡터시간에 간간히 썼던 삼각형의 넓이를 구할 때 두 벡터의 회전 방향에 따라 넓이의 부호가 달라졌다는 점을 이용했네요. 이런 생각을 어떻게 하는거지

대학교 1학년 수학시간에도 같이 다룬 것 같은데 떠올리기 힘들었습니다.

 

CCW 알고리즘이 앞으로 언젠가 쓰이길 바라네요