11758 CCW _python

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

11758번: CCW

제목보고 이해못했으면 검색부터 해보는게 맞다고 보는 문제. 진짜 고생했다

 

 

 

 

 

 

 

 

 

 

 

 

 

문제 접근

처음은 완전 틀린 방법으로 풀었다. CCW? 최창원? 뭐 사람이름인가? 알고리즘 이름이다 

CCW(counter clockwise)는 기하학에서 수의 사칙연산처럼 아주 기초적인 것이라고 한다.

 

틀린 방법

이 얘기를 잠시 두고 처음 문제를 접한 방법은 직선방정식을 만드는 것이였다.

그림에서 A는 직선에 위에있고 B는 직선의 아래에 있다.

그래서 직선방정식을 만들어서 위 아래를 판단하면 해결된다고 생각하고 문제를 풀었다.

하지만 50~70퍼에 무조건 틀리게되있다.

왜냐하면 float같이 소수점 연산을 하면 프로그래밍에서 자주 있는 오류로 약간의 오차가 생긴다.

그 오차를 테스크케이스에서 잡아버리기 때문에 무조건 틀리게되니 소수점 연산을 하면 안된다.

그러니 이 방법은 맞는 방법이긴 하나, 문제에서 원하는 풀이가 아니라서 이렇게 풀면 틀린다.

 

 

맞는 방법

정확히는 문제에서 원하는 방법.

CCW알고리즘을 사용하는것. 그래서 제목도 CCW

다른 블로그들중 가장 설명이 좋았던 블로그

https://snowfleur.tistory.com/98

오른손 법칙을 사용해서 푼다.

 

방향을 오른손으로 감싼다고 표시했을때 엄지방향으로 외적이 되서 나온다.

그러니 반시계방향은 위로, 시계방향은 아래로 향할것이다.

너무나도 이쁜 그림판 예시

1->2->3순서는 반시계방향이니 오른손으로 감싸보면 위로 향하게된다.

이 이론으로 풀면되니 외적만 할줄 알면 된다.

1을 A, 2를 B, 3을 C라고 할것이다.

AB와 BC라고 표시하겠다.

우선 AB와 BC를 알아야 한다.

AB는 ((Bx-Ax), (By-Ay))으로 구할수 있다. BC또한 마찬가지

그리고 외적은 역행렬에서 많이보던 ad-bc로 구할 수 있다.

AB[0]*BC[1] - AB[1]*BC[0]

이걸 0보다 큰지 작은지 비교하면 끝.

 

 

 

 

 

 

 

 

 

 

 

 

틀린 코드

import sys
input = sys.stdin.readline

"""
직선 방정식 y-y1 = m (x-x1)
두 점이 주어질때 기울기 = (y2-y1)/(x2-x1)
x=n그래프일때를 기준으로 3번째 좌표가 위냐 아래냐로 판별
첫번째와 두번째 좌표를 이은 선의 방향은 x1과 x2 비교
"""

x1, y1 = map(int,input().split())
x2, y2 = map(int,input().split())
x3, y3 = map(int,input().split())

if x1 == x2:
    if x1==x3:
        print(0)
    elif y1<y2:
        if x3<x1:
            print(-1)
        elif x3>x1:
            print(1)
    elif y1>y2:
        if x3<x1:
            print(1)
        elif x3>x1:
            print(-1)

elif x1 < x2:
    result = (y3-y1) - ((y2-y1)/(x2-x1))*(x3-x1)
    if result > 0:
        print(1)
    elif result < 0:
        print(-1)
    elif result == 0:
        print(0)

elif x1 > x2:
    result = (y3-y1) - ((y2-y1)/(x2-x1))*(x3-x1)
    if result > 0:
        print(-1)
    elif result < 0:
        print(1)
    elif result == 0:
        print(0)

오차때문에 틀린다. 이건 해결할수가 없다. round도 써봤지만 불가능하고 맞았다 하더라도 푼 의미가 없어보여서 그만뒀다.

 

 

 

 

 

 

 

 

 

 

 

문제가 원하는 풀이

import sys
input = sys.stdin.readline

"""
방향을 구하고, 외적 계산 (ad-bc)
"""

#입력
x1, y1 = map(int,input().split())
x2, y2 = map(int,input().split())
x3, y3 = map(int,input().split())

#방향
AB = [(x2-x1),(y2-y1)]
BC = [(x3-x2),(y3-y2)]

#외적
result = AB[0]*BC[1] - AB[1]*BC[0]

if result > 0:
    print(1)
elif result < 0:
    print(-1)
elif result == 0:
    print(0)