[백준]_17387번 : 선분 교차 2(파이썬)

17387번: 선분 교차 2

 

이 문제를 풀기 전에 사전 지식이 많이 필요하다.

 

1. CCW(Counter Clock Wise) 알고리즘

 

2차원 평면에 놓여 있는 점 3개에 대해 상대적인 위치 관계를 외적을 통해서 구할 수 있다. 이 알고리즘을 적용했을 때 양수가 나오면 반시계, 음수면 시계, 0이면 한 직선 위에 점들이 놓여 있는 것이다.

 

결괏값은 점의 연산 순서(A->B->C)에 매우 민감하기 때문에 점들의 순서가 매우 중요하다. 알고리즘 계산법은 여기서 더 알아보자.

 

2. CCW를 활용한 선분의 교차 조건 

 

그래서 결국 세 점의 상대적인 방향을 알아서 선분의 교차 유무를 어떻게 판단할 수 있을까? 두 선분이 교차할 때와 안 할 때를 나눠서 관찰해 보자.

왼쪽을 <그림 1>, 오른쪽을 <그림 2>라고 하자.

 

p1, p2와 p3, p4가 각각 한 직선을 구성하는 직선이라고 가정하자.

 

이때 어느 한 선분의 두 점을 기준(위의 알고리즘 예시에서의 A, B 역할이라고 하자)으로 나머지 선분에 있는 점을 C라고 잡았을 때 한쪽 점을 잡았을 때의 CCW 결과물과 나머지 점을 잡았을 때의 CCW결과물의 곱이 음수면 교차한다고 할 수 있다.

 

예를 들어 <그림 1>에서 p1을 A, p2를 B라고 하자. C가 p3일 때는 세 점의 순서에 의해 시계 방향이 형성되므로 CCW(p1, p2, p3)<0이다. 이제 C가 p4이면 CCW(p1, p2, p4)>0이다. 결국 선분이 교차하려면 점 C의 대상을 달리(p3 or p4) 했을 때 CCW값의 곱이 음수여야 한다. 

 

물론 이것으로 충분하지 않다. p1, p2가 A, B 역할을 해주었다면 이번에는 p3, p4 가 A, B 역할을 검증 차원에서 해주어야 한다. 이 검증을 거쳐 또한 음수가 나오면 이제야 두 선분이 교차한다고 할 수 있는 것이다. 

 

반드시 두 선분을 같이 검증해야 하는 이유는 <그림 2>에서 알 수 있다.

교차하지 않음에도 ccw*ccw 가 음수이다!!

 

---

하지만 아직 큰 문제 하나가 남아 있다. 점이 다른 직선 위에 놓일 때이다.

 

이때는 CCW가 0이 되어 다음 3 가지 상황 중 어느 상황인지 CCW*CCW의 부호만으로는 알 수 없다. 

이 중에서 왼쪽, 중간 경우만 교차로 인정 된다.

왼쪽부터 차례대로 한 점만 교차, 무수히 많은 점이 교차, 교차 없는 평행이다.

 

마지막 경우만 걸러낼 수 있으면 충분하다. 즉 좌표의 대소로 이것을 해결할 수 있다.

 

최종 코드>>

import sys

input = sys.stdin.readline

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

def ccw(x1, y1, x2, y2, x3, y3):
    return  x1*y2 + x2*y3 + x3*y1 - x2*y1 - x3*y2 - x1*y3
    
if ccw(x1, y1, x2, y2, x3, y3)*ccw(x1, y1, x2, y2, x4, y4)==0 and ccw(x3, y3, x4, y4, x1, y1)*ccw(x3, y3, x4, y4, x2, y2)==0: # 네 점이 한 직선 위에 있을 때
    if max(x1,x2)>=min(x3,x4) and min(x1,x2)<=max(x3,x4) and max(y1,y2)>=min(y3,y4) and min(y1,y2)<=max(y3,y4):
        ans=1
# 등호가 붙은 이유는 한 직선 위에 다른 직선의 점이 놓여 있을 수 있기 때문
elif ccw(x1, y1, x2, y2, x3, y3)*ccw(x1, y1, x2, y2, x4, y4)<=0 and ccw(x3, y3, x4, y4, x1, y1)*ccw(x3, y3, x4, y4, x2, y2)<=0:
    ans=1

print(ans)

 

가장 먼저 네 점이 한 직선 위에 전부 있을 때를 살펴본다. 매우 특수한 경우를 먼저 조건문으로 거른 뒤 일반적인 경우를 살피는 전략을 취하였다.