[백준 17386][파이썬] 선분 교차 1

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

17386번: 선분 교차 1

이전 포스팅에서 CCW 알고리즘을 활용하여 선분 교차하는 방법에 대해서 배웠다.

https://growth-coder.tistory.com/163

 

이 방식을 그대로 사용하면 된다.

 

우선 세 점이 일직선 상에 존재하는 경우가 없다고 했으므로 ccw의 값이 0인 경우는 신경쓰지 않아도 된다.

 

그럼 예외 사항은 아래 그림과 같은 경우만 신경쓰면 된다.

이 경우는 선분 AC를 기준으로 한 번, 선분 BD를 기준으로 두 번 계산하면 된다.

 

import sys
input = sys.stdin.readline
def ccw(x1, y1, x2, y2, x3, y3):
    return  x1*y2 + x2*y3 + x3*y1 - x2*y1 - x3*y2 - x1*y3
x1, y1, x2, y2 = map(int, input().split())
x3, y3, x4, y4 = map(int, input().split())
a=ccw(x1, y1, x2, y2, x3, y3)
b=ccw(x1, y1, x2, y2, x4, y4)
c=ccw(x3, y3, x4, y4, x1, y1)
d=ccw(x3, y3, x4, y4, x2, y2)
print(1 if a*b<0 and c*d<0 else 0)