[코딩 테스트 연습(파이썬/Python)] 백준 17387번 _ 선분 교차 2

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

17387번: 선분 교차 2

[문제]

2차원 좌표 평면 위의 두 선분 L1, L2가 주어졌을 때, 두 선분이 교차하는지 아닌지 구해보자. 한 선분의 끝 점이 다른 선분이나 끝 점 위에 있는 것도 교차하는 것이다.

L1의 양 끝 점은 (x1, y1), (x2, y2), L2의 양 끝 점은 (x3, y3), (x4, y4)이다.

 

[입력]

첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다.

[출력]

L1과 L2가 교차하면 1, 아니면 0을 출력한다.

[제한]

• -1,000,000 ≤ x1, y1, x2, y2, x3, y3, x4, y4 ≤ 1,000,000
• x1, y1, x2, y2, x3, y3, x4, y4는 정수

[아이디어]

1) CCW를 이용해 두 선분이 일직선 상에 위치하는지 파악한다.

2) L1의 양 끝 점 (x1, y1)와 L2의 두 점간의 CCW가 반대 방향을 그리고(곱이 음수), 반대로 L2의 양 끝 점 (x1, y1)와 L1의 두 점간의 CCW가 반대 방향을 그린다면 두 선분은 교차한다고 판단할 수 있다.

3) 두 CCW의 곱이 0인 것을 포함해도 되지만, 둘 다 0일 때에는 네 점이 일직선 상에 위치하지만 교점이 없는 경우도 존재할 수 있다.

4) 3)의 경우를 해결하기 위해, 각 점의 상대적 위치를 비교한다. 

 

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

def ccw(a,b,c,d,e,f):
    return (c-a)*(f-b)-(e-a)*(d-b)

def f(a,b,c,d,x,y,xx,yy):
    tmp1 = ccw(a,b,c,d,x,y)*ccw(a,b,c,d,xx,yy)
    tmp2 = ccw(x,y,xx,yy,a,b)*ccw(x,y,xx,yy,c,d)
    if tmp1==tmp2==0:
        return 1 if min(a,c)<=max(x,xx) and min(x,xx)<=max(a,c) and min(b,d)<=max(y,yy) and min(y,yy)<=max(b,d) else 0
    else:
        return int(tmp1<=0 and tmp2<=0)
print(f(x1,y1,x2,y2,x3,y3,x4,y4))

CCW를 기본적으로 이해하고 있어도, 네 점이 일직선 상에 위치하는 케이스를 다루기가 살짝 어렵게 느껴졌다. 갈 길이 멀구나,,