백준 17387 CCW

백준 17387 ←클릭
CCW를 활용한 문제이다. CCW는 counter clock wise로 점 3개가 있을 때 이 점 3개를 이은 선의 방향을 알 수 있다. 방향을 알 수 있는 원리는 간단한데, 한 점을 기준으로 나머지 두 점을 잇는 직선 두개를 그린 다음, 외적 계산을 하면 된다.

변수 설정

CCW(A, B, C): $\overline{AB}$ $\times$ $\overline{AC}$계산을 하는 함수이다. 필자는 파이썬을 썼지만 다른 언어에서는 외적 계산 값이 음수이면 -1, 0이면 0, 양수이면 1을 return하도록 하면 overflow를 피할 수 있을 것이다. 내 코드에서는 그냥 cross()라고 적었는데 보통 CCW()로 적는다.

CCW 아이디어

• 한 선분을 기준으로 나머지 선분의 두 점을 각각 외적 계산을 한다.
  
  
• CCW(A,B,C) * CCW(A,B,D) <= 0 && CCW(C,D,A) * CCW(C,D,B) <=0이면 선분이 교차한다고 판단한다.
  
  
• 단 CCW(A,B,C) * CCW(A,B,D) == 0 && CCW(C,D,A) * CCW(C,D,B) ==0인 경우 중에서 $\overline{AB}$와 $\overline{CD}$가 분리되어 있는 경우는 예외 처리를 한다.

예외 처리하는 부분은 위 그림을 참고하자(그림판으로 그림)

코드

github

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



vt1 = [x1-x2, y1-y2]
vt2 = [x4-x2, y4-y2]
vt3 = [x3-x2, y3-y2]

vt4 = [x4-x3, y4-y3]
vt5 = [x1-x3, y1-y3]
vt6 = [x2-x3, y2-y3]
def cross(arr1,arr2):
    return arr1[0]*arr2[1] - arr1[1]*arr2[0]
    
cr1 = cross(vt1, vt2)
cr2 = cross(vt1, vt3)
cr3 = cross(vt4, vt5)
cr4 = cross(vt4, vt6)

if cr1*cr2 == 0 and cr3*cr4==0:
    if x1 == x2 and x2 == x3 and x3 == x4:
        f_min = min(y1, y2)
        f_max = max(y1, y2)
        s_min = min(y3, y4)
        s_max = max(y3, y4)
            
    else:
        f_min = min(x1, x2)
        f_max = max(x1, x2)
        s_min = min(x3, x4)
        s_max = max(x3, x4)
    if((f_max >= s_min)and(s_max >= f_min)) :
        print(1)
        exit()
    else:
        print(0)
        exit()
        
if cr1*cr2 <= 0 and cr3*cr4<=0:
    print(1)
        
else:
    print(0)

참고

1. 한 점이 곂치는 케이스는 위 벡터 계산 값이 0이 되므로 처리된다.
2. CCW(A,B,C) 와CCW(A,B,D)만으로 문제를 해결하면 $\overline{AB}$기준으로 C와 D가 반대에 있으면서 둔각으로 있는 경우 예외가 발생하기 때문에 $\overline{CD}$를 기준으로 외적을 계산하는 CCW(C,D,A) 와CCW(C,D,B)를 함께 사용해야 한다.

느낀점

저번 방학 때 못풀고 남겨뒀던 문제인데 다시 푸니 풀렸다. 예외 케이스를 생각해 내는 것을 빠르게 했다면 금방 풀었을 듯.

정답 ~.~