[Algorithm][백준 11758][파이썬] CCW 알고리즘을 활용하여 선분의 교차 여부 판단

어떠한 세 점 A, B, C가 다음과 같이 존재한다고 하자.

선분 AB에 대하여 점 C가 왼쪽에 있는지 오른쪽에 있는지 어떻게 판별할 수 있을까?

 

여러가지 방법이 존재하겠지만 외적을 사용하면 쉽게 구할 수 있다.

 

우선 외적의 정의부터 보자. 벡터 u와 벡터 v의 외적을 구하는 공식은 아래와 같다.

https://wikidocs.net/22384

sin 값은 180도를 기준으로 부호가 바뀐다. 0~180도 전까지는 양수, 180도는 0, 180~360도 전까지는 음수이다.

 

위의 점 A, B, C도 이를 이용해보자. 먼저 선분 AB, AC를 만들어본다.

 

양수

 벡터 AB와 벡터 AC의 외적 값이 양수라면 C는 선분 AB의 오른쪽에 존재하는 것이고 음수라면 왼쪽에 존재하는 것이다.

 

다음 그림은 C가 선분 AB의 왼쪽에 있을 때이다. 각도가 180도 넘어가기 때문에 sin 값이 음수가 된다.

이제 이러한 CCW 알고리즘을 사용하여 두 선분의 교차 여부를 판단할 수 있다.

 

아래와 같은 선분이 있다고 하자.

 

AC 선분을 기준으로 B가 오른쪽, D가 왼쪽, 혹은 B가 왼쪽, D가 오른쪽이면 교차한다고 판단할 수 있다.

 

A, C, B와 A, C, D에 대해서 외적 부호를 구하면 된다.

 

각각 순서대로 (x1, y1), (x2, y2), (x2, y3)라고 해보자.

 

아래 그림처럼 초록색 쌍은 더하기, 빨간색 쌍은 빼기로 구하면 된다.

즉, x1*y2 + x2*y3 + x3*y1 - x2*y1 - x3*y2 - x1*y3의 부호를 구하면 된다.

 

파이썬 코드로 나타내면 다음과 같다.

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

ccw (A, C, B) * ccw (A, C, D)의 값이 음수라면 두 선분은 교차하는 것이다. (설명의 편의를 위해 x좌표 y좌표를 합쳐서 점으로 나타냈다)

 

그런데 이 방법은 예외가 존재한다.

위 그림과 같은 경우에 선분 AC를 기준으로 점 D와 B는 둘 다 오른쪽에 있다.

 

그런데 선분 BD를 기준으로 하면 A는 왼쪽에, C는 오른쪽에 존재하기 때문에 이 경우 두 선분이 교차한다고 판단할 가능성이 있다.

 

이럴 경우 선분 AC를 기준으로도 구해보고 선분 BD를 기준으로도 구해봐야 정확한 답을 얻을 수 있다.

 

예외가 하나 더 있는데 바로 ccw의 값이 0이 되는 경우다.

위 그림과 같은 경우에는 바로 겹치는지 바로 확인할 수 없고 교점을 구해서 추가로 확인해줘야 한다.

 

이에 관한 문제가 백준 11758번 문제이다.

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

11758번: CCW

import sys
input = sys.stdin.readline
def ccw(x1, y1, x2, y2, x3, y3):
    return  x1*y2 + x2*y3 + x3*y1 - x2*y1 - x3*y2 - x1*y3
x1, y1 = map(int, input().split())
x2, y2 = map(int, input().split())
x3, y3 = map(int, input().split())
res=ccw(x1, y1, x2, y2, x3, y3)
if res>0:
    print(1)
elif res<0:
    print(-1)
else:
    print(0)