난이도

Gold 3

인증

문제

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

해설 및 후기

이전에 배운 ccw이론이 사용된다. 선분을 이루는 점을 순회하면서(만약 선분 1에 대한 점 a,b와, 선분 2에 대한 점 c,d가 있다면), abc, abd가 이루는 ccw의 방향이 반대인지 확인한다(곱셈의 값이 음수). 또한 cda, cdb가 이루는 ccw의 방향도 확인하여 교차하는 선분인지 최종적으로 판정한다.

제출 코드

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):
    print(1)
else:
    print(0)