[Python] 백준 17387번: 선분 교차 2

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

17387번: 선분 교차 2

 

import sys
input = sys.stdin.readline


def solution():
    ccw123 = ccw(x1, y1, x2, y2, x3, y3)
    ccw124 = ccw(x1, y1, x2, y2, x4, y4)
    ccw341 = ccw(x3, y3, x4, y4, x1, y1)
    ccw342 = ccw(x3, y3, x4, y4, x2, y2)

    # 평행
    if ccw123*ccw124 == 0 and ccw341*ccw342 == 0:
        if mx1 <= mx4 and mx3 <= mx2 and my1 <= my4 and my3 <= my2:
            return 1
    # 교차
    else:
        if ccw123*ccw124 <= 0 and ccw341*ccw342 <= 0:
            return 1

    return 0


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


if __name__ == '__main__':
    x1, y1, x2, y2 = list(map(int, input().split()))
    x3, y3, x4, y4 = list(map(int, input().split()))

    mx1, my1, mx2, my2 = min(x1, x2), min(y1, y2), max(x1, x2), max(y1, y2)
    mx3, my3, mx4, my4 = min(x3, x4), min(y3, y4), max(x3, x4), max(y3, y4)

    print(solution())

 

CCW라는 알고리즘을 썼다. 간략히 설명하자면, 이 알고리즘을 통해 세 점의 위치 관계를 알 수 있다.(벡터의 외적을 통해 도출된 결과이니 참고하자.) ccw()에 p1, p2, p3의 좌표를 전달하며, 리턴하는 값을 D라고 하자. 이 때 경우의 수는 다음과 같다.

 - D > 0이면, 반시계방향

 - D = 0이면, 평행

 - D < 0이면, 시계방향

위의 경우에는, D < 0이다.

 

 

CCW라는 배경지식을 갖췄으면, 이제 이것을 이용한다. solution() 함수는 선분이 교차하는 경우를 찾아서 return 1을 해주며, 결국 교차하는 케이스를 알아내는 조건문을 통과하지 못하였다면 마지막으로 return 0을 해주는 구조이다. 먼저, 두 선이 평행이면서 겹치는 경우를 색출한다. 앞서 말했듯이, 평행인 경우에는 ccw의 리턴값이 0이다. 이를 통해 조건문을 짜준다. 이 때 주의해야할 케이스는 아래와 같다.

이 때문에, ccw를 4번이나 참조해주는 것이다.

 

이제, 평행인 경우를 찾아냈으므로, 팽행이면서 겹치는 경우를 찾아야한다. 이것은 단순히 4개의 값을 비교하면 된다.

 

 

다음은 일반적인 교차하는 경우이다. 설명에 앞서, 아래는 (거의) 모든 경우의 수이다.

이것을 일반화해보면, 아래 코드와 같다.

if ccw123*ccw124 <= 0 and ccw341*ccw342 <= 0:

그림으로 설명하자면 다음과 같다.