난이도

Gold 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는 정수 선분의 길이는 0보다 크다.

예제 입력

1 1 5 5
1 5 5 1

예제 출력

1

해설 및 후기

선분 교차 1과 유사하나 결정적인 부분이 다르다. 각 점을 이루는 선분들이 일직선을 형성할 수 있다는 것이다. 이러한 경우에는 우선 ccw가 모두 0인지를 판정 후에(모두 일직선), 선분이 포개어져있는가를 분기문으로 추가해 해결할 수 있다.

제출 코드

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

def ccw(a,b,c):
    res = (b[0]-a[0])*(c[1]-a[1])-(c[0]-a[0])*(b[1]-a[1])
    return res
a = ccw([x1,y1],[x2,y2],[x3,y3])*ccw([x1,y1],[x2,y2],[x4,y4])
b = ccw([x3,y3],[x4,y4],[x1,y1])*ccw([x3,y3],[x4,y4],[x2,y2])
if(a == 0 and b == 0):
    if min(x1, x2) <= max(x3, x4) and min(x3, x4) <= max(x1, x2) and min(y1, y2) <= max(y3, y4) and min(y3, y4) <= max(y1, y2):  
        print(1)
    else:
        print(0)
elif(a <= 0 and b <= 0):
    print(1)
else:
    print(0)